Path: ...!eternal-september.org!feeder2.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 45
Date: Mon, 11 Nov 2024 03:17:24 -0000
Organization: A noiseless patient Spider
Lines: 1817
Message-ID: <pAVkKS8fFJ0cWyM9LAymZEjIw3-YV4Uu@eprint.iacr.org.invalid>
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Mon, 11 Nov 2024 04:17:30 +0100 (CET)
Injection-Info: dont-email.me; posting-host="f160f54bd2075053206d0102f37cfb0d";
	logging-data="849648"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/vPctV2UFPFxxE+K9UGPEQxTcjAddlXFM="
Cancel-Lock: sha1:IQkn0cwAAeLjoRHDBGh2Ay8Zd7o=
Bytes: 97557

## In this issue

1. [2023/1401] On the Multi-User Security of LWE-based NIKE
2. [2024/1800] Privacy-Preserving Multi-Party Search via ...
3. [2024/1801] Investigation of the Optimal Linear Characteristics ...
4. [2024/1802] ColliderScript: Covenants in Bitcoin via 160-bit ...
5. [2024/1803] Siniel: Distributed Privacy-Preserving zkSNARK
6. [2024/1804] Quantum Chosen-Cipher Attack on Camellia
7. [2024/1805] Smoothing Parameter and Shortest Vector Problem on ...
8. [2024/1806] Encrypted RAM Delegation: Applications to Rate-1 ...
9. [2024/1807] An Unstoppable Ideal Functionality for Signatures ...
10. [2024/1808] Breaking BASS
11. [2024/1809] Foundations of Adaptor Signatures
12. [2024/1810] Linear Proximity Gap for Reed-Solomon Codes within ...
13. [2024/1811] Pseudorandom Function-like States from Common Haar ...
14. [2024/1812] Batching Adaptively-Sound SNARGs for NP
15. [2024/1813] Revisiting Leakage-Resilient MACs and Succinctly- ...
16. [2024/1814] SophOMR: Improved Oblivious Message Retrieval from ...
17. [2024/1815] Succinct Randomized Encodings from Non-compact ...
18. [2024/1816] Attacking Automotive RKE Security: How Smart are ...
19. [2024/1817] Improved ML-DSA Hardware Implementation With First ...
20. [2024/1818] SoK: On the Physical Security of UOV-based ...
21. [2024/1819] VCVio: A Formally Verified Forking Lemma and Fiat- ...
22. [2024/1820] On the Power of Oblivious State Preparation
23. [2024/1821] SCIF: Privacy-Preserving Statistics Collection with ...
24. [2024/1822] Anonymous Public-Key Quantum Money and Quantum Voting
25. [2024/1823] A Composability Treatment of Bitcoin's Transaction ...
26. [2024/1824] Constructing Dembowski=E2=80=93Ostrom permutation ...
27. [2024/1825] BrakingBase - a linear prover, poly-logarithmic ...
28. [2024/1826] Cloning Games, Black Holes and Cryptography
29. [2024/1827] OPTIMSM: FPGA hardware accelerator for Zero- ...
30. [2024/1828] Classic McEliece Hardware Implementation with ...
31. [2024/1829] Compiled Nonlocal Games from any Trapdoor Claw-Free ...
32. [2024/1830] A Tight Analysis of GHOST Consistency
33. [2024/1831] Fast Two-party Threshold ECDSA with Proactive Security
34. [2024/1832] How to Delete Without a Trace: Certified ...
35. [2024/1833] Private Neural Network Training with Packed Secret ...
36. [2024/1834] Scutum: Temporal Verification for Cross-Rollup ...
37. [2024/1835] Hybrid Zero-Knowledge from Garbled Circuits
38. [2024/1836] Symmetric Encryption on a Quantum Computer
39. [2024/1837] A Query Reconstruction Attack on the Chase-Shen ...
40. [2024/1838] Pushing the QAM method for finding APN functions ...
41. [2024/1839] Cryptographically Secure Digital Consent
42. [2024/1840] Ideal Pseudorandom Codes
43. [2024/1841] Verifying Jolt zkVM Lookup Semantics
44. [2024/1842] Zero-Knowledge Location Privacy via Accurate ...
45. [2024/1843] Khatam: Reducing the Communication Complexity of ...
46. [2024/1844] KLaPoTi: An asymptotically efficient isogeny group ...
47. [2024/1845] Single-Server Client Preprocessing PIR with Tight ...
48. [2024/1846] The LaZer Library: Lattice-Based Zero Knowledge and ...
49. [2024/1847] Notions of Quantum Reductions and Impossibility of ...
50. [2024/1848] Non-Interactive Zero-Knowledge Proofs with ...

## 2023/1401

* Title: On the Multi-User Security of LWE-based NIKE
* Authors: Roman Langrehr
* [Permalink](https://eprint.iacr.org/2023/1401)
* [Download](https://eprint.iacr.org/2023/1401.pdf)

### Abstract

Non-interactive key exchange (NIKE) schemes like the Diffie-Hellman key excha=
nge are a widespread building block in several cryptographic protocols. Since=
 the Diffie-Hellman key exchange is not post-quantum secure, it is important =
to investigate post-quantum alternatives.

We analyze the security of the LWE-based NIKE by Ding et al. (ePrint 2012) an=
d Peikert (PQCrypt 2014) in a multi-user setting where the same public key is=
 used to generate shared keys with multiple other users. The Diffie-Hellman k=
ey exchange achieves this security notion. The mentioned LWE-based NIKE schem=
e comes with an inherent correctness error (Guo et al., PKC 2020), and this h=
as significant implications for the multi-user security, necessitating a clos=
er examination.

Single-user security generically implies multi-user security when all users g=
enerate their keys honestly for NIKE schemes with negligible correctness erro=
r. However, the LWE-based NIKE requires a super-polynomial modulus to achieve=
 a negligible correctness error, which makes the scheme less efficient. We sh=
ow that
  - generically, single-user security does not imply multi-user security when=
 the correctness error is non-negligible, but despite this
  - the LWE-based NIKE with polynomial modulus is multi-user secure for hones=
t users when the number of users is fixed in advance. This result takes advan=
tage of the leakage-resilience properties of LWE.

We then turn to a stronger model of multi-user security that allows adversari=
ally generated public keys. For this model, we consider a variant of the LWE-=
based NIKE where each public key is equipped with a NIZKPoK of the secret key=
.. Adding NIZKPoKs is a standard technique for this stronger model and Hesse e=
t al. (Crypto 2018) showed that this is sufficient to achieve security in the=
 stronger multi-user security model for perfectly correct NIKEs (which the LW=
E-based NIKE is not). We show that
  - for certain parameters that include all parameters with polynomial modulu=
s, the LWE-based NIKE can be efficiently attacked with adversarially generate=
d public keys, despite the use of NIZKPoKs, but
  - for suitable parameters (that require a super-polynomial modulus), this s=
ecurity notion is achieved by the LWE-based NIKE with NIZKPoKs.
This stronger security notion has been previously achieved for LWE-based NIKE=
 only in the QROM, while all our results are in the standard model.



## 2024/1800

* Title: Privacy-Preserving Multi-Party Search via Homomorphic Encryption wit=
h Constant Multiplicative Depth
* Authors: Mihail-Iulian Ple=C5=9Fa, Ruxandra F. Olimid
* [Permalink](https://eprint.iacr.org/2024/1800)
* [Download](https://eprint.iacr.org/2024/1800.pdf)

### Abstract

We propose a privacy-preserving multiparty search protocol
using threshold-level homomorphic encryption, which we prove correct
and secure to honest but curious adversaries. Unlike existing approaches,
our protocol maintains a constant circuit depth. This feature enhances
its suitability for practical applications involving dynamic underlying
databases.



## 2024/1801

* Title: Investigation of the Optimal Linear Characteristics of BAKSHEESH (Fu=
ll Version)
* Authors: Yuxuan Peng, Jinpeng Liu, Ling Sun
* [Permalink](https://eprint.iacr.org/2024/1801)
* [Download](https://eprint.iacr.org/2024/1801.pdf)

### Abstract

This paper aims to provide a more comprehensive understanding of the optimal =
linear characteristics of BAKSHEESH. Initially, an explicit formula for the a=
bsolute correlation of the $R$-round optimal linear characteristic of BAKSHEE=
SH is proposed when $R \geqslant 12$. By examining the linear characteristics=
 of BAKSHEESH with three active S-boxes per round, we derive some properties =
of the three active S-boxes in each round. Furthermore, we demonstrate that t=
here is only one 1-round iterative linear characteristic with three active S-=
boxes. Since the 1-round linear characteristic is unique, it must be included=
 in any $R$-round ($R \geqslant 12$) linear characteristics of BAKSHEESH with=
 three active S-boxes per round. Finally, we confirm that BAKSHEESH's total n=
umber of $R$-round optimal linear characteristics is $3072$ for $R \geqslant =
12$. All of these characteristics are generated by employing the 1-round iter=
ative linear characteristic.



## 2024/1802

* Title: ColliderScript: Covenants in Bitcoin via 160-bit hash collisions
* Authors: Ethan Heilman, Victor I. Kolobov, Avihu M. Levy, Andrew Poelstra
* [Permalink](https://eprint.iacr.org/2024/1802)
* [Download](https://eprint.iacr.org/2024/1802.pdf)

### Abstract

We introduce a method for enforcing covenants on Bitcoin outputs without requ=
iring any changes to Bitcoin by designing a hash collision based equivalence =
check which bridges Bitcoin's limited Big Script to Bitcoin's Small Script. T=
his allows us evaluate the signature of the spending transaction (available o=
nly to Big Script) in Small Script. As Small Script enables arbitrary computa=
tions, we can introspect into the spending transaction and enforce covenants =
on it.

Our approach leverages finding collisions in the $160$-bit hash functions: SH=
A-1 and RIPEMD-160. By the birthday bound this should cost  $\sim2^{80}$ work=
.. Each spend of our covenant costs $\sim2^{86}$ hash queries and $\sim2^{56}$=
 bytes of space. For security, we rely on an assumption regarding the hardnes=
s of finding a $3$-way collision (with short inputs) in $160$-bit hash functi=
ons, arguing that if the assumption holds, breaking covenant enforcement requ=
ires $\sim2^{110}$ hash queries. To put this in perspective, the work to spen=
d our covenant is $\sim33$ hours of the Bitcoin mining network, whereas break=
ing our covenant requires $\sim 450,000$ years of the Bitcoin mining network.
We believe there are multiple directions of future work that can significantl=
y improve these numbers.

Evaluating covenants and our equivalence check requires performing many opera=
tions in Small Script, which must take no more than $4$ megabytes in total si=
ze, as Bitcoin does not allow transactions greater than $4$ megabytes.  We on=
ly provide rough estimates of the transaction size because, as of this writin=
g, no Small Script implementations of the hash functions required, SHA-1 and =
RIPEMD-160, have been written.
========== REMAINDER OF ARTICLE TRUNCATED ==========