Path: ...!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: IACR ePrint Archive <noreply@example.invalid>
Newsgroups: sci.crypt
Subject: [digest] 2024 Week 17
Date: Mon, 29 Apr 2024 02:31:09 -0000
Organization: A noiseless patient Spider
Lines: 1301
Message-ID: <oEg2ux-Rl-zbenhdGILhvlnoEyYMVbzV@eprint.iacr.org.invalid>
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Mon, 29 Apr 2024 04:31:14 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="7672f4b57ee3afc1fc6c3e9d43d7d556";
	logging-data="1588457"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+tuqVWnC+JOFBE/LVRnLme9YB48rTWXxs="
Cancel-Lock: sha1:bJh55lsA+PVE1n4WY5wJtBOuKWo=
Bytes: 68974

## 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=C3=B6ttling, 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 h=
ashing key such that the digest statistically binds the input at $m$ secret l=
ocations. This hash function is said to be somewhere extractable (SE) if ther=
e is an additional trapdoor that allows the extraction of the input bits at t=
he $m$ locations from the digest.=20

     Devadas, Goyal, Kalai, and Vaikuntanathan (FOCS 2022) introduced a varia=
nt of somewhere extractable hashing called rate-1 fully local SE hash functio=
ns. 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 sh=
owing 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 p=
articular, 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 e=
xtractable hash function from Decisional Diffie-Hellman (DDH) and BARGs. Unde=
r the same assumptions, we give constructions of rate-1 BARG and RAM SNARG wi=
th partial input soundness whose proof sizes are only matched by prior constr=
uctions based on LWE.



## 2024/561

* Title: SQIAsignHD: SQIsignHD Adaptor Signature
* Authors: Farzin Renan, P=C3=A9ter 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 digita=
l signature schemes where a secret randomness is hidden within a signature. A=
daptor signatures are a recent cryptographic primitive and are becoming an im=
portant tool for blockchain applications such as cryptocurrencies to reduce o=
n-chain costs, improve fungibility, and contribute to off-chain forms of paym=
ent in payment-channel networks, payment-channel hubs, and atomic swaps. Howe=
ver, currently used adaptor signature constructions are vulnerable to quantum=
 adversaries due to Shor's algorithm. In this work, we introduce $\mathsf{SQI=
AsignHD}$, a new quantum-resistant adaptor signature scheme based on isogenie=
s of supersingular elliptic curves, using SQIsignHD - as the underlying signa=
ture scheme - and exploiting the idea of the artificial orientation on the su=
persingular isogeny Diffie-Hellman key exchange protocol, SIDH, as the underl=
ying hard relation. We, furthermore, show that our scheme is secure in the Qu=
antum 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 ch=
oice without revealing any message to the signer. Round-optimal blind signatu=
res are designed as a two-round interactive protocol between a signer and rec=
eiver. Coincidentally, the choice of message is not important in many applica=
tions, and is routinely set as a random (unstructured) message by a receiver.
With the goal of designing more efficient blind signatures for such applicati=
ons, Hanzlik (Eurocrypt '23) introduced a new variant called non-interactive =
blind signatures (NIBS). These allow a signer to asynchronously generate part=
ial signatures for any recipient such that only the intended recipient can ex=
tract a blinded signature for a random message. This bypasses the two-round b=
arrier for traditional blind signatures, yet enables many known applications.
Hanzlik provided new practical designs for NIBS from bilinear pairings. In th=
is work, we investigate efficient NIBS with post-quantum security. We design =
the first practical NIBS, as well as non-interactive partially blind signatur=
es 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 crypt=
ographic community regarding the potential subversion of cryptographic system=
s. Bellare et al. (CRYPTO'14) introduced the notion of Algorithm Substitution=
 Attacks (ASAs), which aim to covertly leak sensitive information by undermin=
ing individual cryptographic primitives. In this work, we delve deeply into t=
he realm of ASAs against protocols built upon cryptographic primitives. In pa=
rticular, we revisit the existing ASA model proposed by Berndt et al. (AsiaCC=
S'22), providing a more fine-grained perspective. We introduce a novel ASA mo=
del tailored for protocols, capable of capturing a wide spectrum of subversio=
n attacks. Our model features a modular representation of subverted parties w=
ithin protocols, along with fine-grained definitions of undetectability. To i=
llustrate 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 offer=
s a comprehensive ASA model suited to cryptographic protocols, providing a us=
eful 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 construc=
t a zero-knowledge proof (ZKP) system, which is a notable privacy-enhancing t=
echnology. We propose a novel efficient IPA called $\mathsf{Cougar}$. $\maths=
f{Cougar}$ features cubic root verifier and logarithmic communication under t=
he 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 ac=
hieve this, we combine two distinct square root IPAs from Kim et al.: one wit=
h pairing ($\mathsf{Protocol3}$) and one without pairing ($\mathsf{Protocol4}=
========== REMAINDER OF ARTICLE TRUNCATED ==========