[digest] 2024 Week 17

Liste des GroupesRevenir à s crypt 
Sujet : [digest] 2024 Week 17
De : noreply (at) *nospam* example.invalid (IACR ePrint Archive)
Groupes : sci.crypt
Date : 29. Apr 2024, 03:31:09
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <oEg2ux-Rl-zbenhdGILhvlnoEyYMVbzV@eprint.iacr.org.invalid>
## 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

The conditional disclosure of secrets (CDS) primitive is among the simplest cryptographic settings in which to study the relationship between communication, randomness, and security. CDS involves two parties, Alice and Bob, who do not communicate but who wish to reveal a secret $z$ to a referee if and only if a Boolean function $f$ has $f(x,y)=1$. Alice knows $x,z$, Bob knows $y$, and the referee knows $x,y$. Recently, a quantum analogue of this primitive called CDQS was defined and related to f-routing, a task studied in the context of quantum position-verification. CDQS has the same inputs, outputs, and communication pattern as CDS but allows the use of shared entanglement and quantum messages. We initiate the systematic study of CDQS, with the aim of better understanding the relationship between privacy and quantum resources in the information theoretic setting. We begin by looking for quantum analogues of results already established in the classical CDS literature. Doing so we establish a number of basic properties of CDQS, including lower bounds on entanglement and communication stated in terms of measures of communication complexity. Because of the close relationship to the $f$-routing position-verification scheme, our results have relevance to the security of these schemes.



## 2024/631

* Title: BackMon: IC Backside Tamper Detection using On-Chip Impedance Monitoring
* Authors: Tahoura Mosavirik, Shahin Tajik
* [Permalink](https://eprint.iacr.org/2024/631)
* [Download](https://eprint.iacr.org/2024/631.pdf)

### Abstract

The expansion of flip-chip technologies and a lack of backside protection make the integrated circuit (IC) vulnerable to certain classes of physical attacks mounted from the IC’s backside. Laser-assisted probing, electromagnetic, and body-basing injection attacks are examples of such attacks. Unfortunately, there are few countermeasures proposed in the literature, and none are available commercially. Those that do exist are not only expensive but are incompatible with current IC manufacturing processes. They also cannot be integrated into legacy systems, such as field programmable gate arrays (FPGAs), which are integral parts of many of the industrial and defense systems. In this paper, we demonstrate how the impedance monitoring of the printed circuit board (PCB) and IC package’s power distribution network (PDN) using on-chip circuit-based network analyzers can detect IC backside tampering. Our method is based on the fact that any tampering attempt to expose the backside silicon substrate, such as the removal of the fan and heat sinks, leads to changes in the equivalent impedance of the package’s PDN, and hence, scanning the package impedance will reveal whether the package integrity has been violated. To validate our claims, we deploy an on-FPGA network analyzer on an AMD Zynq UltraScale+ MPSoC manufactured with 16 nm technology, which is part of a multi-PCB system. We conduct a series of experiments at different temperatures, leveraging the difference of means as the statistical metric, to demonstrate the effectiveness of our method in detecting tamper events required to expose the IC backside silicon.



## 2024/632

* Title: Further Investigations on Nonlinear Complexity of Periodic Binary Sequences
* Authors: Qin Yuan, Chunlei Li, Xiangyong Zeng, Tor Helleseth, Debiao He
* [Permalink](https://eprint.iacr.org/2024/632)
* [Download](https://eprint.iacr.org/2024/632.pdf)

### Abstract

Nonlinear complexity is an important measure for assessing the randomness of sequences. In this paper we investigate how circular shifts affect the nonlinear complexities of finite-length binary sequences and then reveal a more explicit relation between nonlinear complexities of finite-length binary sequences and their corresponding periodic sequences. Based on the relation, we propose two algorithms that can generate all periodic binary sequences with any prescribed nonlinear complexity.



## 2024/633

* Title: Vision Mark-32: ZK-Friendly Hash Function Over Binary Tower Fields
* Authors: Tomer Ashur, Mohammad Mahzoun, Jim Posen, Danilo Šijačić
* [Permalink](https://eprint.iacr.org/2024/633)
* [Download](https://eprint.iacr.org/2024/633.pdf)

### Abstract

Zero-knowledge proof systems are widely used in different applications on the Internet.
Among zero-knowledge proof systems, SNARKs are a popular choice because of their fast verification time and small proof size.
The efficiency of zero-knowledge systems is crucial for usability, resulting in the development of so-called arithmetization-oriented ciphers.
In this work, we introduce Vision Mark-32, a modified instance of Vision defined over binary tower fields, with an optimized number of rounds and an efficient MDS matrix.
We implement a fully-pipelined Vision Mark-32 permutation on Alveo U55C FPGA accelerator card and argue an order of magnitude better hardware efficiency compared to the popular Poseidon hash.
Our fully-pipelined Vision Mark-32 implementation runs at 250 MHz and uses 398 kLUT and 104 kFF.
Lastly, we delineate how to implement each step efficiently in hardware.



## 2024/634

* Title: NTRU-based FHE for Larger Key and Message Space
* Authors: Robin Jadoul, Axel Mertens, Jeongeun Park, Hilder V. L. Pereira
* [Permalink](https://eprint.iacr.org/2024/634)
* [Download](https://eprint.iacr.org/2024/634.pdf)

### Abstract

The NTRU problem has proven a useful building block for efficient bootstrapping in Fully Homomorphic Encryption (FHE) schemes, and different such schemes have been proposed. FINAL (ASIACRYPT 2022) first constructed FHE using homomorphic multiplexer (CMux) gates for the blind rotation operation. Later, XZD+23 (CRYPTO 2023) gave an asymptotic optimization by changing the ciphertext format to enable ring automorphism evaluations. In this work, we examine an adaptation to FINAL to evaluate CMux gates of higher arity and the resulting tradeoff to running times and bootstrapping key sizes. In this setting, we can compare the time and space efficiency of both bootstrapping protocols with larger key space against each other and the state of the art.



## 2024/635

* Title: Organizing Records for Retrieval in Multi-Dimensional Range Searchable Encryption
* Authors: Mahdieh Heidaripour, Ladan Kian, Maryam Rezapour, Mark Holcomb, Benjamin Fuller, Gagan Agrawal, Hoda Maleki
* [Permalink](https://eprint.iacr.org/2024/635)
* [Download](https://eprint.iacr.org/2024/635.pdf)

### Abstract

Storage of sensitive multi-dimensional arrays must be secure and efficient in storage and processing time. Searchable encryption allows one to trade between security and efficiency. Searchable encryption design focuses on building indexes, overlooking the crucial aspect of record retrieval. Gui et al. (PoPETS 2023) showed that understanding the security and efficiency of record retrieval is critical to understand the overall system. A common technique for improving security is partitioning data tuples into parts. When a tuple is requested, the entire relevant part is retrieved, hiding the tuple of interest.
This work assesses tuple partitioning strategies in the dense data setting, considering parts that are random, $1$-dimensional, and multi-dimensional. We consider synthetic datasets of $2$, $3$ and $4$ dimensions, with sizes extending up to $2$M tuples. We compare security and efficiency across a variety of record retrieval methods. Our findings are:
1. For most configurations, multi-dimensional partitioning yields better efficiency and less leakage.
2. 1-dimensional partitioning outperforms multi-dimensional partitioning when the first (indexed) dimension is any size as long as the query is large in all other dimensions except the (the first dimension can be any size).
3. The leakage of 1-dimensional partitioning is reduced the most when using a bucketed ORAM (Demertiz et al., USENIX Security 2020).



## 2024/636

* Title: Regev Factoring Beyond Fibonacci: Optimizing Prefactors
* Authors: Seyoon Ragavan
* [Permalink](https://eprint.iacr.org/2024/636)
* [Download](https://eprint.iacr.org/2024/636.pdf)

### Abstract

In this note, we improve the space-efficient variant of Regev's quantum factoring algorithm [Reg23] proposed by Ragavan and Vaikuntanathan [RV24] by constant factors in space and/or size. This allows us to bridge the significant gaps in concrete efficiency between the circuits by [Reg23] and [RV24]; [Reg23] uses far fewer gates, while [RV24] uses far fewer qubits.
   
The main observation is that the space-efficient quantum modular exponentiation technique by [RV24] can be modified to work with more general sequences of integers than the Fibonacci numbers. We parametrize this in terms of a linear recurrence relation, and through this formulation construct three different circuits for quantum factoring:
        - A circuit that uses $\approx 12.4n$ qubits and $\approx 54.9n^{1/2}$ multiplications of $n$-bit integers.
        - A circuit that uses $(9+\epsilon)n$ qubits and $O_\epsilon(n^{1/2})$ multiplications of $n$-bit integers, for any $\epsilon > 0$.
        - A circuit that uses $(24+\epsilon)n^{1/2}$ multiplications of $n$-bit integers, and $O_\epsilon(n)$ qubits, for any $\epsilon > 0$.

In comparison, the original circuit by [Reg23] uses at least $\approx 3n^{3/2}$ qubits and $\approx 6n^{1/2}$ multiplications of $n$-bit integers, while the space-efficient variant by [RV24] uses $\approx 10.32n$ qubits and $\approx 138.3n^{1/2}$ multiplications of $n$-bit integers (although a very simple modification of their Fibonacci-based circuit uses $\approx 11.32n$ qubits and only $\approx 103.7n^{1/2}$ multiplications of $n$-bit integers). The improvements proposed in this note take effect for sufficiently large values of $n$; it remains to be seen whether they can also provide benefits for practical problem sizes.



## 2024/637

* Title: Towards Permissionless Consensus in the Standard Model via Fine-Grained Complexity
* Authors: Marshall Ball, Juan Garay, Peter Hall, Aggelos Kiayias, Giorgos Panagiotakos
* [Permalink](https://eprint.iacr.org/2024/637)
* [Download](https://eprint.iacr.org/2024/637.pdf)

### Abstract

We investigate the feasibility of permissionless consensus (aka Byzantine agreement) under standard assumptions. A number of protocols have been proposed to achieve permissionless consensus, most notably based on the Bitcoin protocol; however, to date no protocol is known that can be provably instantiated outside of the random oracle model.

In this work, we take the first steps towards achieving permissionless consensus in the standard model. In particular, we demonstrate that worst-case conjectures in fine-grained complexity, in particular the orthogonal vectors conjecture (implied by the Strong Exponential Time Hypothesis), imply permissionless consensus in the random beacon model—a setting where a fresh random value is delivered to all parties at regular intervals. This gives a remarkable win-win result: either permissionless consensus exists relative to a random beacon, or there are non-trivial worst-case algorithmic speed-ups for a host of natural algorithmic problems (including SAT).

Our protocol achieves resilience against adversaries that control an inverse-polynomial fraction of the honest computational power, i.e., adversarial power $A = T^{1−ε} $ for some constant $ε > 0$, where $T$ denotes the honest computational power. This relatively low threshold is a byproduct of the slack in the fine-grained complexity conjectures.

One technical highlight is the construction of a Seeded Proof of Work: a Proof of Work where many (correlated) challenges can be derived from a single short public seed, and yet still no non-trivial amortization is possible.



## 2024/638

* Title: A note on ``a lightweight mutual and transitive authentication mechanism for IoT network''
* Authors: Zhengjun Cao, Lihua Liu
* [Permalink](https://eprint.iacr.org/2024/638)
* [Download](https://eprint.iacr.org/2024/638.pdf)

### Abstract

We show the authentication mechanism [Ad Hoc Networks, 2023, 103003]  fails to keep user anonymity, not as claimed.



## 2024/639

* Title: Computational Attestations of Polynomial Integrity Towards Verifiable Machine Learning
* Authors: Dustin Ray, Caroline El Jazmi
* [Permalink](https://eprint.iacr.org/2024/639)
* [Download](https://eprint.iacr.org/2024/639.pdf)

### Abstract

Machine-learning systems continue to advance at a rapid pace, demonstrating remarkable utility in various fields and disciplines. As these systems continue to grow in size and complexity, a nascent industry is emerging which aims to bring machine-learning-as-a-service (MLaaS) to market. Outsourcing the operation and training of these systems to powerful hardware carries numerous advantages, but challenges arise when needing to ensure privacy and the correctness of work carried out by a potentially untrusted party. Recent advancements in the discipline of applied zero-knowledge cryptography, and probabilistic proof systems in general, have led to a means of generating proofs of integrity for any computation, which in turn can be efficiently verified by any party, in any place, at any time.

In this work we present the application of a non-interactive, plausibly-post-quantum-secure, probabilistically-checkable argument system utilized as an efficiently verifiable guarantee that a privacy mechanism was irrefutably applied to a machine-learning model during the training process. That is, we prove the correct training of a differentially-private (DP) linear regression over a dataset of 60,000 samples on a single machine in 55 minutes, verifying the entire computation in 47 seconds. To our knowledge, this result represents the fastest known instance in the literature of provable-DP over a dataset of this size. Finally, we show how this task can be run in parallel, leading to further dramatic reductions in prover and verifier runtime complexity. We believe this result constitutes a key stepping-stone towards end-to-end private MLaaS.



## 2024/640

* Title: On Proving Pairings
* Authors: Andrija Novakovic, Liam Eagen
* [Permalink](https://eprint.iacr.org/2024/640)
* [Download](https://eprint.iacr.org/2024/640.pdf)

### Abstract

In this paper we explore efficient ways to prove correctness of elliptic curve pairing relations. Pairing-based cryptographic protocols such as the Groth16 and Plonk SNARKs and the BLS signature scheme are used extensively in public blockchains such as Ethereum due in large part to their small size. However the relatively high cost of pairing computation remains a practical problem for many use cases such as verification ``in circuit" inside a SNARK. This naturally arises in recursive SNARK composition and SNARKs of BLS based consensus protocols.

To improve pairing verification, we first show that the final exponentiation step of pairing verification can be replaced with a more efficient ``residue check," which can be incorporated into the Miller loop. Then, we show how to reduce the cost of the Miller loop by pre-computing all the necessary lines, and how this is especially efficient when the second pairing argument is fixed in advance. This is the case for BLS signatures with a fixed public key, as well as for KZG based SNARKs like Plonk and two of the three Groth16 pairings. Finally, we show how to improve of the protocol of [gar] by combining quotients, which allows us to more efficiently prove higher degree relations. These techniques also carry over naturally to pairing verification, for example on-chain verification or as part of the BitVM(2) protocol for Bitcoin smart contracts. We instantiate algorithms and show results for the BN254 curve.



## 2024/641

* Title: Rondo: Scalable and Reconfiguration-Friendly Randomness Beacon
* Authors: Xuanji Meng, Xiao Sui, Zhaoxin Yang, Kang Rong, Wenbo Xu, Shenglong Chen, Ying Yan, Sisi Duan
* [Permalink](https://eprint.iacr.org/2024/641)
* [Download](https://eprint.iacr.org/2024/641.pdf)

### Abstract

We present Rondo, a scalable and reconfiguration-friendly distributed randomness beacon (DRB) protocol in the partially synchronous model. Rondo is the first DRB protocol that is built from batched asynchronous verifiable secret sharing (bAVSS) and meanwhile avoids the high $O(n^3)$ message cost, where $n$ is the number of nodes. Our key contribution lies in the introduction of a new variant of bAVSS called batched asynchronous verifiable secret sharing with partial output (bAVSS-PO). bAVSS-PO is a weaker primitive than bAVSS but allows us to build a secure and more efficient DRB protocol. We propose a bAVSS-PO protocol Breeze. Breeze achieves the optimal $O(n)$ messages for the sharing stage and allows Rondo to offer better scalability than prior DRB protocols. 
Additionally, to support the reconfiguration, we introduce Rondo-BFT, a dynamic and partially synchronous Byzantine fault-tolerant protocol inspired by Dyno (S&P 2022). Unlike Dyno, Rondo-BFT provides a communication pattern that  generates  randomness beacon output periodically, making it well-suited for DRB applications.

We implement our protocols and evaluate the performance on Amazon EC2 using up to 91 instances. Our evaluation results show that Rondo achieves higher throughput than existing works and meanwhile offers better scalability, where the performance does not degrade as significantly as $n$ grows.



## 2024/642

* Title: GraphOS: Towards Oblivious Graph Processing
* Authors: Javad Ghareh Chamani, Ioannis Demertzis, Dimitrios Papadopoulos, Charalampos Papamanthou, Rasool Jalili
* [Permalink](https://eprint.iacr.org/2024/642)
* [Download](https://eprint.iacr.org/2024/642.pdf)

### Abstract

We propose GraphOS, a system that allows a client that owns a graph database to outsource it to an untrusted server for storage and querying. It relies on doubly-oblivious primitives and trusted hardware to achieve a very strong privacy and efficiency notion which we call oblivious graph processing: the server learns nothing besides the number of graph vertexes and edges, and for each query its type and response size. At a technical level, GraphOS stores the graph on a doubly-oblivious data structure, so that all vertex/edge accesses are indistinguishable. For this purpose, we propose Omix++, a novel doubly-oblivious map that outperforms the previous state of the art by up to 34×, and may be of independent interest. Moreover, to avoid any leakage from CPU instruction fetching during query evaluation, we propose algorithms for four fundamental graph queries (BFS/DFS traversal, minimum spanning tree, and single-source shortest paths) that have a fixed execution trace, i.e., the sequence of executed operations is independent of the input. By combining these techniques, we eliminate all information that a hardware adversary observing the memory access pattern within the protected enclave can infer. We benchmarked GraphOS against the best existing solution, based on oblivious relational DBMS(translating graph queries to relational operators). GraphOS is not only significantly more performant (by up to two orders of magnitude for our tested graphs) but it eliminates leakage related to the graph topology that is practically inherent when a relational DBMS is used unless all operations are “padded” to the worst case.



## 2024/643

* Title: Key-Homomorphic and Aggregate Verifiable Random Functions
* Authors: Giulio Malavolta
* [Permalink](https://eprint.iacr.org/2024/643)
* [Download](https://eprint.iacr.org/2024/643.pdf)

### Abstract

A verifiable random function (VRF) allows one to compute a random-looking image, while at the same time providing a unique proof that the function was evaluated correctly. VRFs are a cornerstone of modern cryptography and, among other applications, are at the heart of recently proposed proof-of-stake consensus protocols. In this work we initiate the formal study of aggregate VRFs, i..e., VRFs that allow for the aggregation of proofs/images into a small di- gest, whose size is independent of the number of input proofs/images, yet it still enables sound verification. We formalize this notion along with its security properties and we propose two constructions: The first scheme is conceptually simple, concretely efficient, and uses (asymmetric) bilinear groups of prime order. Pseudorandomness holds in the random oracle model and aggregate pseudorandomness is proven in the algebraic group model. The second scheme is in the standard model and it is proven secure against the learning with errors (LWE) problem.

As a cryptographic building block of independent interest, we introduce the notion of key homomorphic VRFs, where the verification keys and the proofs are endowed with a group structure. We conclude by discussing several applications of key-homomorphic and aggregate VRFs, such as distributed VRFs and aggregate proof-of-stake protocols.



## 2024/644

* Title: Jumping for Bernstein-Yang Inversion
* Authors: Li-Jie Jian, Ting-Yuan Wang, Bo-Yin Yang, Ming-Shing Chen
* [Permalink](https://eprint.iacr.org/2024/644)
* [Download](https://eprint.iacr.org/2024/644.pdf)

### Abstract

This paper achieves fast polynomial inverse operations specifically tailored for the NTRU Prime KEM on ARMv8 NEON instruction set benchmarking on four processor architectures: Cortex-A53, Cortex-A72, Cortex-A76 and Apple M1. We utilize the jumping divison steps of the constant-time GCD algorithm from Bernstein and Yang (TCHES’19) and optimize underlying polynomial multiplication of various lengths to improve the efficiency for computing polynomial inverse operations in NTRU Prime.



## 2024/645

* Title: Toward Independent Key Encryption based on Q-Problem
* Authors: Abdelkader Laouid, Mostefa Kara, Mohammad Hammoudeh
* [Permalink](https://eprint.iacr.org/2024/645)
* [Download](https://eprint.iacr.org/2024/645.pdf)

### Abstract

This paper defines a post-quantum encryption scheme based on discussion cryptography by introducing a new post-quantum hard problem called Q-Problem. The idea behind this scheme is to hide the keys of each entity, and the encryption process is based on secret message holders using only random private keys.



## 2024/646

* Title: Efficient Quantum Algorithm for SUBSET-SUM Problem
* Authors: Sanchita Ghosh, Anant Sharma, Sreetama Das, Shibdas Roy
* [Permalink](https://eprint.iacr.org/2024/646)
* [Download](https://eprint.iacr.org/2024/646.pdf)

### Abstract

Problems in the complexity class $NP$ are not all known to be solvable, but are verifiable given the solution, in polynomial time by a classical computer. The complexity class $BQP$ includes all problems solvable in polynomial time by a quantum computer. Prime factorization is in $NP$ class, and is also in $BQP$ class, owing to Shor's algorithm. The hardest of all problems within the $NP$ class are called $NP$-complete. If a quantum algorithm can solve an $NP$-complete problem in polynomial time, it would imply that a quantum computer can solve all problems in $NP$ in polynomial time. Here, we present a polynomial-time quantum algorithm to solve an $NP$-complete variant of the $SUBSET-SUM$ problem, thereby, rendering $NP\subseteq BQP$. We illustrate that given a set of integers, which may be positive or negative, a quantum computer can decide in polynomial time whether there exists any subset that sums to zero. There are many real-world applications of our result, such as finding patterns efficiently in stock-market data, or in recordings of the weather or brain activity. As an example, the decision problem of matching two images in image processing is $NP$-complete, and can be solved in polynomial time, when amplitude amplification is not required.



## 2024/647

* Title: Weightwise (almost) perfectly balanced functions based on total orders
* Authors: Pierrick Méaux
* [Permalink](https://eprint.iacr.org/2024/647)
* [Download](https://eprint.iacr.org/2024/647.pdf)

### Abstract

he unique design of the FLIP cipher necessitated a generalization of standard cryptographic criteria for Boolean functions used in stream ciphers, prompting a focus on properties specific to subsets of $\mathbb{F}_2^n$ rather than the entire set. This led to heightened interest in properties related to fixed Hamming weight sets and the corresponding partition of $\mathbb{F}_2^n$ into n+1 such sets. Consequently, the concept of Weightwise Almost Perfectly Balanced (WAPB) functions emerged, which are balanced on each of these sets.Various studies have since proposed WAPB constructions and examined their cryptographic parameters for use in stream cipher filters.

In this article, we introduce a general approach to constructing WAPB functions using the concept of order, which simplifies implementation and enhances cryptographic strength. We present two new constructions: a recursive method employing multiple orders on binary strings, and another utilizing just two orders. We establish lower bounds for nonlinearity and weightwise nonlinearities within these classes. By instantiating specific orders, we demonstrate that some achieve minimal algebraic immunity, while others provide functions with guaranteed optimal algebraic immunity. Experimental results in 8 and 16 variables indicate that using orders based on field representation significantly outperforms other methods in terms of both global and weightwise algebraic immunity and nonlinearity. Additionally, we extend the recursive construction to create WAPB functions for any value of n, with experiments in 10, 12, and 14 variables confirming that these order-based functions exhibit robust cryptographic parameters. In particular, those based on field orders display optimal degrees and algebraic immunity, and strong weightwise nonlinearities and algebraic immunities.



## 2024/648

* Title: Encrypted KNN Implementation on Distributed Edge Device Network
* Authors: B Pradeep Kumar Reddy, Ruchika Meel, Ayantika Chatterjee
* [Permalink](https://eprint.iacr.org/2024/648)
* [Download](https://eprint.iacr.org/2024/648.pdf)

### Abstract

Machine learning (ML) as a service has emerged as a rapidly expanding field across various industries like
healthcare, finance, marketing, retail and e-commerce, Industry 4.0, etc where a huge amount of data is gen-
erated. To handle this amount of data, huge computational power is required for which cloud computing used
to be the first choice. However, there are several challenges in cloud computing like limitations of bandwidth,
network connectivity, higher latency, etc. To address these issues, edge computing is prominent nowadays,
where the data from sensor nodes is collected and processed on low-cost edge devices. As simple sensor
nodes are not capable of handling complex computations of ML models, data from sensor nodes need to be
transferred to some nearest edge devices for further processing. If this sensor data is related to some security-
critical application, the privacy of such sensitive data needs to be preserved both during communication from
sensor node to edge device and computation in edge nodes. This increased need to perform edge-based ML
on privacy-preserved data has led to a surge in interest in homomorphic encryption (HE) due to its ability to
perform computations on encrypted form of data. The highest form of HE, Fully Homomorphic Encryption
(FHE), is capable of theoretically handling arbitrary encrypted algorithms but comes with huge computational
overhead. Hence, the implementation of such a complex encrypted ML model on a single edge node is not
very practical in terms of latency requirements. Our paper introduces a low-cost encrypted ML framework on
a distributed edge cluster, where multiple low-cost edge devices (Raspberry Pi boards) are clustered to perform
encrypted distributed K-Nearest Neighbours (KNN) algorithm computations. Our experimental result shows,
KNN prediction on standard Wisconsin breast cancer dataset takes approximately 1.2 hours, implemented on
a cluster of six pi boards, maintaining end-to-end data confidentiality of critical medical data without any re-
quirement of costly cloud-based computation resource support



## 2024/649

* Title: Sphinx-in-the-Head: Group Signatures from Symmetric Primitives
* Authors: Liqun Chen, Changyu Dong, Christopher J. P. Newton, Yalan Wang
* [Permalink](https://eprint.iacr.org/2024/649)
* [Download](https://eprint.iacr.org/2024/649.pdf)

### Abstract

Group signatures and their variants have been widely used in privacy-sensitive scenarios such as anonymous authentication and attestation. In this paper, we present a new post-quantum group signature scheme from symmetric primitives. Using only symmetric primitives makes the scheme less prone to unknown attacks than basing the design on newly proposed hard problems whose security is less well-understood. However, symmetric primitives do not have rich algebraic properties, and this makes it extremely challenging to design a group signature scheme on top of them. It is even more challenging if we want a group signature scheme suitable for real-world applications, one that can support large groups and require few trust assumptions. Our scheme is based on MPC-in-the-head non-interactive zero-knowledge proofs, and we specifically design a novel hash-based group credential scheme, which is rooted in the SPHINCS+ signature scheme but with various modifications to make it MPC (multi-party computation) friendly. The security of the scheme has been proved under the fully dynamic group signature model. We provide an implementation of the scheme and demonstrate the feasibility of handling a group size as large as $2^{60}$. This is the first group signature scheme from symmetric primitives that supports such a large group size and meets all the security requirements.



## 2024/650

* Title: Hash-based Direct Anonymous Attestation
* Authors: Liqun Chen, Changyu Dong, Nada El Kassem, Christopher J.P. Newton, Yalan Wang
* [Permalink](https://eprint.iacr.org/2024/650)
* [Download](https://eprint.iacr.org/2024/650.pdf)

### Abstract

Direct Anonymous Attestation (DAA) was designed for the Trusted Platform Module (TPM) and versions using RSA and elliptic curve cryptography have been included in the TPM specifications and in ISO/IEC standards. These standardised DAA schemes have their security based on the factoring or discrete logarithm problems and are therefore insecure against quantum attackers. Research into quantum-resistant DAA has resulted in several lattice-based schemes. Now in this paper, we propose the first post-quantum DAA scheme from symmetric primitives. We make use of a hash-based signature scheme, which is a slight modification of SPHINCS+, as a DAA credential. A DAA signature, proving  the possession of such a credential, is a multiparty computation-based non-interactive zero-knowledge proof. The security of our scheme is proved under the Universal Composability (UC) model. While maintaining all the security properties required for a DAA scheme, we try to make the TPM's workload as low as possible. Our DAA scheme can handle a large group size (up to $2^{60}$ group members), which meets the requirements of rapidly developing TPM applications.



## 2024/651

* Title: A New Hash-based Enhanced Privacy ID Signature Scheme
* Authors: Liqun Chen, Changyu Dong, Nada El Kassem, Christopher J.P. Newton, Yalan Wang
* [Permalink](https://eprint.iacr.org/2024/651)
* [Download](https://eprint.iacr.org/2024/651.pdf)

### Abstract

The elliptic curve-based Enhanced Privacy ID (EPID) signature scheme is broadly used for hardware enclave attestation by many platforms that implement Intel Software Guard Extensions (SGX) and other devices. This scheme has also been included in the Trusted Platform Module (TPM) specifications and ISO/IEC standards. However, it is insecure against quantum attackers. While research into quantum-resistant EPID has resulted in several lattice-based schemes, Boneh et al. have initiated the study of EPID signature schemes built only from symmetric primitives. We observe that for this line of research, there is still room for improvement. In this paper, we propose a new hash-based EPID scheme, which includes a novel and efficient signature revocation scheme. In addition, our scheme can handle a large group size (up to $2^{60}$ group members), which meets the requirements of rapidly developing hardware enclave attestation applications. The security of our scheme is proved under the Universal Composability (UC) model. Finally, we have implemented our EPID scheme, which, to our best knowledge, is the first implementation of EPID from symmetric primitives.



## 2024/652

* Title: Compact and Secure Zero-Knowledge Proofs for Quantum-Resistant Cryptography from Modular Lattice Innovations
* Authors: Samuel Lavery
* [Permalink](https://eprint.iacr.org/2024/652)
* [Download](https://eprint.iacr.org/2024/652.pdf)

### Abstract

This paper presents a comprehensive security analysis of the Adh zero-knowledge proof system, a novel lattice-based, quantum-resistant proof of possession system. The Adh system offers compact key and proof sizes, making it suitable for real-world digital signature and public key agreement protocols. We explore its security by reducing it to the hardness of the Module-ISIS problem and introduce three new variants: Module-ISIS+, Module-ISIS*, and Module-ISIS**. These constructions enhance security through variations on chaining mechanisms. We also provide a reduction to the module modulus subset sum problem under conservative assumptions.

Empirical evidence and statistical testing support the zero-knowledge, completeness, and soundness properties of the Adh proof system. Comparative analysis demonstrates the Adh system's advantages in terms of key and proof sizes over existing post-quantum schemes like Kyber and Dilithium.

This paper represents an early preprint and is a work in progress. The core security arguments and experimental results are present, and formal proofs and additional analysis are provided. We invite feedback and collaboration from the research community to further strengthen the security foundations of the Adh system and explore its potential applications in quantum-resistant cryptography.

Date Sujet#  Auteur
29 Apr 24 o [digest] 2024 Week 171IACR ePrint Archive

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal