[continued from previous message]

Blockchain-enabled digital currency systems have typically operated in isolation, lacking necessary mechanisms for seamless interconnection. Consequently, transferring assets across distinct currency systems remains a complex challenge, with existing
schemes often falling short in ensuring security, privacy, and practicality. This paper proposes P2C2T -- a privacy-preserving cross-chain transfer scheme. It is the first scheme to address atomicity, unlinkability, indistinguishability, non-
collateralization, and required functionalities across diverse currency systems. P2C2T is based on \textit{threshold anonymous atomic locks} (TA$^2$L), also proposed by us, serving as the cornerstone for guaranteeing atomic cross-chain transfer while
obscuring the payment relationships between users. By combining TA$^2$L with \textit{verifiable timed discrete logarithm} schemes, P2C2T renders cross-chain transactions indistinguishable from regular intra-chain ones. Notably, P2C2T eliminates the
collateralization of senders and imposes minimal requirements on underlying blockchains, specifically on the ability to verify signatures. We substantiate the security of TA$^2$L based on a proposed cryptographic notion called \textit{threshold blind
conditional signatures} and demonstrate the security of P2C2T through necessary proofs. Additionally, we compare the performance of P2C2T with an existing scheme that has properties closest to P2C2T. The comparison reveals that P2C2T reduces overhead by
at least $85.488\%$ in terms of running time, communication cost, and storage cost when completing a cross-chain transfer. We further conduct cross-chain transfers and intra-chain payments using the Bitcoin testnet and Litecoin testnet to illustrate the
privacy and practicality of P2C2T.



## 2024/1468

* Title: Dense and smooth lattices in any genus
* Authors: Wessel van Woerden
* [Permalink](https://eprint.iacr.org/2024/1468)
* [Download](https://eprint.iacr.org/2024/1468.pdf)

### Abstract

The Lattice Isomorphism Problem (LIP) was recently introduced as a new hardness assumption for post-quantum cryptography.
The strongest known efficiently computable invariant for LIP is the genus of a lattice.
To instantiate LIP-based schemes one often requires the existence of a lattice that (1) lies in some fixed genus, and (2) has some good geometric properties such as a high packing density or small smoothness parameter.

In this work we show that such lattices exist. In particular, building upon classical results by Siegel (1935), we show that essentially any genus contains a lattice with a close to optimal packing density, smoothing parameter and covering radius.
We present both how to efficiently compute concrete existence bounds for any genus, and asymptotically tight bounds under weak conditions on the genus.



## 2024/1469

* Title: Password-Protected Threshold Signatures
* Authors: Stefan Dziembowski, Stanislaw Jarecki, Paweł Kędzior, Hugo Krawczyk, Chan Nam Ngo, Jiayu Xu
* [Permalink](https://eprint.iacr.org/2024/1469)
* [Download](https://eprint.iacr.org/2024/1469.pdf)

### Abstract

We witness an increase in applications like cryptocurrency wallets, which involve users issuing signatures using private keys. To protect these keys from loss or compromise, users commonly outsource them to a custodial server. This creates a new point of
failure, because compromise of such a server leaks the user’s key, and if user authentication is implemented with a password then this password becomes open to an offline dictionary attack (ODA). A better solution is to secret-share the key among a set
of servers, possibly including user’s own device(s), and implement password authentication and signature computation using threshold cryptography.

We propose a notion of augmented password protected threshold signature scheme (aptSIG) which captures the best possible security level for this setting. Using standard threshold cryptography techniques, i.e. threshold password authentication and
threshold signatures, one can guarantee that compromising up to t out of n servers reveals no information on either the key or the password. However, we extend this with a novel property, namely that compromising even all n servers also does not leak any
information, except via an unavoidable ODA attack, which reveals the key (and the password) only if the attacker guesses the password.

We define aptSIG in the Universally Composable (UC) framework and show that it can be constructed very efficiently, using a black-box composition of any UC threshold signature and a UC augmented Password-Protected Secret Sharing (aPPSS), which we define
as an extension of prior notion of PPSS. As concrete instantiations we obtain secure aptSIG schemes for ECDSA and BLS signatures with very small overhead over the respective threshold signature.

Finally, we note that both the notion and our generic solution for augmented password-protected threshold signatures can be generalized to password-protecting MPC for any keyed functions.



## 2024/1470

* Title: Quantum Pseudorandom Scramblers
* Authors: Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, Mingnan Zhao
* [Permalink](https://eprint.iacr.org/2024/1470)
* [Download](https://eprint.iacr.org/2024/1470.pdf)

### Abstract

Quantum pseudorandom state generators (PRSGs) have stimulated exciting developments in recent years. A PRSG, on a fixed initial (e.g., all-zero) state, produces an output state that is computationally indistinguishable from a Haar random state. However,
pseudorandomness of the output state is not guaranteed on other initial states. In fact, known PRSG constructions provably fail on some initial states.

In this work, we propose and construct quantum Pseudorandom State Scramblers (PRSSs), which can produce a pseudorandom state on an arbitrary initial state. In the information-theoretical setting, we obtain a scrambler which maps an arbitrary initial
state to a distribution of quantum states that is close to Haar random in total variation distance. As a result, our scrambler exhibits a dispersing property. Loosely, it can span an ɛ-net of the state space. This significantly strengthens what standard
PRSGs can induce, as they may only concentrate on a small region of the state space provided that average output state approximates a Haar random state.

Our PRSS construction develops a parallel extension of the famous Kac's walk, and we show that it mixes exponentially faster than the standard Kac's walk. This constitutes the core of our proof. We also describe a few applications of PRSSs. While our
PRSS construction assumes a post-quantum one-way function, PRSSs are potentially a weaker primitive and can be separated from one-way functions in a relativized world similar to standard PRSGs.



## 2024/1471

* Title: Communication Efficient Secure and Private Multi-Party Deep Learning
* Authors: Sankha Das, Sayak Ray Chowdhury, Nishanth Chandran, Divya Gupta, Satya Lokam, Rahul Sharma
* [Permalink](https://eprint.iacr.org/2024/1471)
* [Download](https://eprint.iacr.org/2024/1471.pdf)

### Abstract

Distributed training that enables multiple parties to jointly train
a model on their respective datasets is a promising approach to
address the challenges of large volumes of diverse data for training
modern machine learning models. However, this approach immedi-
ately raises security and privacy concerns; both about each party
wishing to protect its data from other parties during training and
preventing leakage of private information from the model after
training through various inference attacks. In this paper, we ad-
dress both these concerns simultaneously by designing efficient
Differentially Private, secure Multiparty Computation (DP-MPC)
protocols for jointly training a model on data distributed among
multiple parties. Our DP-MPC protocol in the two-party setting
is 56-794× more communication-efficient and 16-182× faster than
previous such protocols. Conceptually, our work simplifies and
improves on previous attempts to combine techniques from secure
multiparty computation and differential privacy, especially in the
context of ML training.



## 2024/1472

* Title: Isogeny-Based Secure Voting Systems for Large-Scale Elections
* Authors: Mohammed El Baraka, Siham Ezzouak
* [Permalink](https://eprint.iacr.org/2024/1472)
* [Download](https://eprint.iacr.org/2024/1472.pdf)

### Abstract

This article presents an in-depth study of isogeny-based cryptographic methods for the development of secure and scalable electronic voting systems. We address critical challenges such as voter privacy, vote integrity, and resistance to quantum attacks.
Our work introduces novel cryptographic protocols leveraging isogenies, establishing a robust framework for post-quantum secure electronic voting. We provide detailed mathematical foundations, protocol designs, and security proofs, demonstrating the
efficacy and scalability of our proposed system in large-scale elections.



## 2024/1473

* Title: A Note on Low-Communication Secure Multiparty Computation via Circuit Depth-Reduction
* Authors: Pierre Charbit, Geoffroy Couteau, Pierre Meyer, Reza Naserasr
* [Permalink](https://eprint.iacr.org/2024/1473)
* [Download](https://eprint.iacr.org/2024/1473.pdf)

### Abstract

We consider the graph-theoretic problem of removing (few) nodes from a directed acyclic graph in order to reduce its depth. While this problem is intractable in the general case, we provide a variety of algorithms in the case where the graph is that of a
circuit of fan-in (at most) two, and explore applications of these algorithms to secure multiparty computation with low communication. Over the past few years, a paradigm for low-communication secure multiparty computation has found success based on
decomposing a circuit into low-depth ``chunks''. This approach was however previously limited to circuits with a ``layered'' structure. Our graph-theoretic approach extends this paradigm to all circuits. In particular, we obtain the following
contributions:

1) Fractionally linear-communication MPC in the correlated randomness model: We provide an $N$-party protocol for computing an $n$-input, $m$-output $\mathsf{F}$-arithmetic circuit with $s$ internal gates (over any basis of binary gates) with
communication complexity $(\frac{2}{3}s + n + m)\cdot N\cdot\log |\mathsf{F}|$, which can be improved to $((1+\epsilon)\cdot\frac{2}{5}s+n+m)\cdot N\cdot\log |\mathsf{F}|$ (at the cost of increasing the computational overhead from a small constant factor
to a large one). Previously, comparable protocols either used more than $s\cdot N\cdot \log |\mathsf{F}|$ bits of communication, required super-polynomial computation, were restricted to layered circuits, or tolerated a sub-optimal corruption threshold.

2) Sublinear-Communication MPC:
Assuming the existence of $N$-party Homomorphic Secret Sharing for logarithmic depth circuits (respectively doubly logarithmic depth circuits), we show there exists sublinear-communication secure $N$-party computation for \emph{all} $\log^{1+o(1)}$-depth
(resp.~$(\log\log)^{1+o(1)}$-depth) circuits. Previously, this result was limited to $(\mathcal{O}(\log))$-depth (resp.~$(\mathcal{O}(\log\log))$-depth) circuits, or to circuits with a specific structure (e.g. layered).

3) The 1-out-of-M-OT complexity of MPC:
We introduce the `` 1-out-of-M-OT complexity of MPC'' of a function $f$, denoted $C_M(f)$, as the number of oracle calls required to securely compute $f$ in the 1-out-of-M-OT hybrid model. We establish the following upper bound: for every $M\geq 2$, $C_
N(f) \leq (1+g(M))\cdot \frac{2 |f|}{5}$, where $g(M)$ is an explicit vanishing function.

We also obtain additional contributions to reducing the amount of bootstrapping for fully homomorphic encryption, and to other types of sublinear-communication MPC protocols such as those based on correlated symmetric private information retrieval.



## 2024/1474

* Title: Mystrium: Wide Block Encryption Efficient on Entry-Level Processors
* Authors: Parisa Amiri Eliasi, Koustabh Ghosh, Joan Daemen
* [Permalink](https://eprint.iacr.org/2024/1474)
* [Download](https://eprint.iacr.org/2024/1474.pdf)

### Abstract

We present a tweakable wide block cipher called Mystrium and show it as the fastest such primitive on low-end processors that lack dedicated AES or other cryptographic instructions, such as ARM Cortex-A7.
Mystrium is based on the provably secure double-decker mode, that requires a doubly extendable cryptographic keyed (deck) function and a universal hash function.
We build a new deck function called Xymmer that for its compression part uses Multimixer-128, the fastest universal hash for such processors, and for its expansion part uses a newly designed permutation, $\mathcal{G}_{512}$.
Deck functions can also be used in modes to build encryption, authenticated encryption, and authentication schemes, and hence, Xymmer is of independent interest.
The current state-of-the-art wide tweakable block cipher Adiantum-XChaCha12-AES encrypts 4096-byte messages at 11.5 cycles per byte on ARM Cortex-A7, while for Mystrium it is 6.8 cycles per byte while having a higher claimed security.



## 2024/1475

* Title: On the Spinor Genus and the Distinguishing Lattice Isomorphism Problem * Authors: Cong Ling, Jingbo Liu, Andrew Mendelsohn
* [Permalink](https://eprint.iacr.org/2024/1475)
* [Download](https://eprint.iacr.org/2024/1475.pdf)

### Abstract

This paper addresses the spinor genus, a previously unrecognized classification of quadratic forms in the context of cryptography, related to the lattice isomorphism problem (LIP). The spinor genus lies between the genus and equivalence class, thus
refining the concept of genus. We present algorithms to determine whether two quadratic forms belong to the same spinor genus. If they do not, it provides a negative answer to the distinguishing variant of LIP. However, these algorithms have very high
complexity, and we show that the proportion of genera splitting into multiple spinor genera is vanishing (assuming rank $n \geq 3$). For the special case of anisotropic integral binary forms ($n = 2$) over number fields with class number 1, we offer an
efficient quantum algorithm to test if two forms lie in the same spinor genus. Our algorithm does not apply to the HAWK protocol, which uses integral binary Hermitian forms over number fields with class number greater than 1.



## 2024/1476

* Title: The Concrete Security of Two-Party Computation: Simple Definitions, and Tight Proofs for PSI and OPRFs
* Authors: Mihir Bellare, Rishabh Ranjan, Doreen Riepel, Ali Aldakheel
* [Permalink](https://eprint.iacr.org/2024/1476)
* [Download](https://eprint.iacr.org/2024/1476.pdf)

### Abstract

This paper initiates a concrete-security treatment of two-party secure computation. The first step is to propose, as target, a simple, indistinguishability-based definition that we call InI. This could be considered a poor choice if it were weaker than
standard simulation-based definitions, but it is not; we show that for functionalities satisfying a condition called invertibility, that we define and show is met by functionalities of practical interest like PSI and its variants, the two definitions are
equivalent. Based on this, we move forward to study the concrete security of a canonical OPRF-based construction of PSI, giving a tight proof of InI security of the constructed PSI protocol based on the security of the OPRF. This leads us to the concrete
security of OPRFs, where we show how different DH-style assumptions on the underlying group yield proofs of different degrees of tightness, including some that are tight, for the well-known and efficient 2H-DH OPRF, and thus for the corresponding DH PSI
protocol. We then give a new PSI protocol, called salted-DH PSI, that is as efficient as DH-PSI, yet enjoys tighter proofs.



## 2024/1477

* Title: Signature-based Witness Encryption with Compact Ciphertext
* Authors: Gennaro Avitabile, Nico Döttling, Bernardo Magri, Christos Sakkas, Stella Wohnig
* [Permalink](https://eprint.iacr.org/2024/1477)
* [Download](https://eprint.iacr.org/2024/1477.pdf)

### Abstract

Signature-based witness encryption (SWE) is a recently proposed notion that allows to encrypt a message with respect to a tag $T$ and a set of signature verification keys. The resulting ciphertext can only be decrypted by a party who holds at least $k$
different valid signatures w.r.t. $T$ and $k$ different verification keys out of the $n$ keys specified at encryption time. Natural applications of this primitive involve distributed settings (e.g., blockchains), where multiple parties sign predictable
messages, such as polling or randomness beacons. However, known SWE schemes without trusted setup have ciphertexts that scale linearly in the number of verification keys. This quickly becomes a major bottleneck as the system gets more distributed and the
number of parties increases.

Towards showing the feasibility of SWE with ciphertext size sub-linear in the number of keys, we give a construction based on indistinguishability obfuscation (iO) for Turing machines and strongly puncturable signatures (SPS).



## 2024/1478

* Title: Mind the Bad Norms: Revisiting Compressed Oracle-based Quantum Indistinguishability Proofs
* Authors: Ritam Bhaumik, Benoît Cogliati, Jordan Ethan, Ashwin Jha
* [Permalink](https://eprint.iacr.org/2024/1478)
* [Download](https://eprint.iacr.org/2024/1478.pdf)

### Abstract

In this work, we revisit the Hosoyamada-Iwata (HI) proof for the quantum CPA security of the 4-round Luby-Rackoff construction and identify a gap that appears to undermine the security proof. We emphasize that this is not an attack, and the construction
may still achieve the claimed security level. However, this gap raises concerns about the feasibility of establishing a formal security proof for the 4-round Luby-Rackoff construction. In fact, the issue persists even if the number of rounds is increased
arbitrarily. On a positive note, we restore the security of the 4-round Luby-Rackoff construction in the non-adaptive setting, achieving security up to $2^{n/6}$ superposition queries. Furthermore, we establish the quantum CPA security of the 4-round
MistyR and 5-round MistyL constructions, up to $2^{n/5}$ and $2^{n/7}$ superposition queries, respectively, where $n$ denotes the size of the underlying permutation.

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