## 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.