[continued from previous message]

In this work, we develop a new array of techniques that we use to construct a quantum state obfuscator, a powerful notion formalized recently by Coladangelo and Gunn (arXiv:2311.07794) in their pursuit of better software copy-protection schemes. Quantum
state obfuscation refers to the task of compiling a quantum program, consisting of a quantum circuit $C$ with a classical description and an auxiliary quantum state $\ket{\psi}$, into a functionally-equivalent obfuscated quantum program that hides as
much as possible about $C$ and $\ket{\psi}$. We prove the security of our obfuscator when applied to any pseudo-deterministic quantum program, i.e. one that computes a (nearly) deterministic classical input / classical output functionality. Our security
proof is with respect to an efficient classical oracle, which may be heuristically instantiated using quantum-secure indistinguishability obfuscation for classical circuits.

Our result improves upon the recent work of Bartusek, Kitagawa, Nishimaki and Yamakawa (STOC 2023) who also showed how to obfuscate pseudo-deterministic quantum circuits in the classical oracle model, but only ones with a completely classical description.
Furthermore, our result answers a question of Coladangelo and Gunn, who provide a construction of quantum state indistinguishability obfuscation with respect to a quantum oracle, but leave the existence of a concrete real-world candidate as an open
problem. Indeed, our quantum state obfuscator together with Coladangelo-Gunn gives the first candidate realization of a ``best-possible'' copy-protection scheme for all polynomial-time functionalities.

Our techniques deviate significantly from previous works on quantum obfuscation. We develop several novel technical tools which we expect to be broadly useful in quantum cryptography. These tools include a publicly-verifiable, linearly-homomorphic
quantum authentication scheme with classically-decodable ZX measurements (which we build from coset states), and a method for compiling any quantum circuit into a "linear + measurement" ($\LM$) quantum program: an alternating sequence of CNOT operations
and partial ZX measurements.



## 2024/83

* Title: Layout Graphs, Random Walks and the t-wise Independence of SPN Block Ciphers
* Authors: Tianren Liu, Angelos Pelecanos, Stefano Tessaro, Vinod Vaikuntanathan
* [Permalink](https://eprint.iacr.org/2024/083)
* [Download](https://eprint.iacr.org/2024/083.pdf)

### Abstract

We continue the study of $t$-wise independence of substitution-permutation networks (SPNs) initiated by the recent work of Liu, Tessaro, and Vaikuntanathan (CRYPTO 2021).
Our key technical result shows that when the S-boxes are randomly and independently chosen and kept secret, an $r$-round SPN with input length $n = b \cdot k$ is $2^{-\Theta(n)}$-close to $t$-wise independent within $r = O(\min\{k, \log t\})$ rounds for
any $t$ almost as large as $2^{b/2}$. Here, $b$ is the input length of the S-box and we assume that the underlying mixing achieves maximum branch number.
We also analyze the special case of AES parameters (with random S-boxes), and show it is $2^{-128}$-close to pairwise independent in $7$ rounds.
Central to our result is the analysis of a random walk on what we call the layout graph, a combinatorial abstraction that captures equality and inequality constraints among multiple SPN evaluations.
We use our technical result to show concrete security bounds for SPNs with actual block cipher parameters and small-input $S$-boxes. (This is in contrast to the large body of results on ideal-model analyses of SPNs.) For example, for the censored-AES
block cipher, namely AES with most of the mixing layers removed, we show that 192 rounds suffice to attain $2^{-128}$-closeness to pairwise independence. The prior such result for AES (Liu, Tessaro and Vaikuntanathan, CRYPTO 2021) required more than 9000
rounds.



## 2024/84

* Title: Efficient Instances of Docked Double Decker With AES
* Authors: Christoph Dobraunig, Krystian Matusiewicz, Bart Mennink, Alexander Tereschenko
* [Permalink](https://eprint.iacr.org/2024/084)
* [Download](https://eprint.iacr.org/2024/084.pdf)

### Abstract

A tweakable wide blockcipher is a construction which behaves in the same way as a tweakable blockcipher, with the difference that the actual block size is flexible. Due to this feature, a tweakable wide blockcipher can be directly used as a strong
encryption scheme that provides full diffusion when encrypting plaintexts to ciphertexts and vice versa. Furthermore, it can be the basis of authenticated encryption schemes fulfilling the strongest security notions. In this paper, we present two
instantiations of the docked double decker tweakable wide blockcipher: $\mathit{ddd}\text{-}\mathit{AES}$ and $\mathit{bbb}\text{-}\mathit{ddd}\text{-}\mathit{AES}$. Both instances exclusively use similar building blocks as AES-GCM (AES and finite field
multiplication), are designed for maximal parallelism, and hence, can make efficient use of existing hardware accelerators. Moreover, $\mathit{bbb}\text{-}\mathit{ddd}\text{-}\mathit{AES}$ builds upon a novel beyond birthday bound secure pseudorandom
function, a tweakable variant of the XOR of permutations, facilitating in the need to include a tweak in the AES evaluations without sacrificing flexibility in docked double decker.



## 2024/85

* Title: Simultaneously simple universal and indifferentiable hashing to elliptic curves
* Authors: Dmitrii Koshelev
* [Permalink](https://eprint.iacr.org/2024/085)
* [Download](https://eprint.iacr.org/2024/085.pdf)

### Abstract

The present article explains how to generalize the hash function SwiftEC (in an elementary quasi-unified way) to any elliptic curve $E$ over any finite field $\mathbb{F}_{\!q}$ of characteristic $> 3$. The new result apparently brings the theory of hash
functions onto elliptic curves to its logical conclusion. To be more precise, this article provides compact formulas that define a hash function $\{0,1\}^* \to E(\mathbb{F}_{\!q})$ (deterministic and indifferentible from a random oracle) with the same
working principle as SwiftEC. In particular, both of them equally compute only one square root in $\mathbb{F}_{\!q}$ (in addition to two cheap Legendre symbols). However, the new hash function is valid with much more liberal conditions than SwiftEC,
namely when $3 \mid q-1$. Since in the opposite case $3 \mid q-2$ there are already indifferentiable constant-time hash functions to $E$ with the cost of one root in $\mathbb{F}_{\!q}$, this case is not processed in the article. If desired, its approach
nonetheless allows to easily do that mutatis mutandis.



## 2024/86

* Title: On Hilbert-Poincaré series of affine semi-regular polynomial sequences and related Gröbner bases
* Authors: Momonari Kudo, Kazuhiro Yokoyama
* [Permalink](https://eprint.iacr.org/2024/086)
* [Download](https://eprint.iacr.org/2024/086.pdf)

### Abstract

Gröbner bases are nowadays central tools for solving various problems in commutative algebra and algebraic geometry.
A typical use of Gröbner bases is the multivariate polynomial system solving, which enables us to construct algebraic attacks against post-quantum cryptographic protocols.
Therefore, the determination of the complexity of computing Gröbner bases is very important both in theory and in practice:
One of the most important cases is the case where input polynomials compose an (overdetermined) affine semi-regular sequence.
The first part of this paper aims to present a survey on the Gröbner basis computation and its complexity.
In the second part, we shall give an explicit formula on the (truncated) Hilbert-Poincaré series associated to the homogenization of an affine semi-regular sequence.
Based on the formula, we also study (reduced) Gröbner bases of
the ideals generated by an affine semi-regular sequence and its homogenization.
Some of our results are considered to give mathematically rigorous proofs of the correctness of methods for computing Gröbner bases of the ideal generated by an affine semi-regular sequence.



## 2024/87

* Title: Tree-based Lookup Table on Batched Encrypted Queries using Homomorphic Encryption
* Authors: Jung Hee Cheon, Hyeongmin Choe, Jai Hyun Park
* [Permalink](https://eprint.iacr.org/2024/087)
* [Download](https://eprint.iacr.org/2024/087.pdf)

### Abstract

Homomorphic encryption (HE) is in the spotlight as a solution for privacy-related issues in various real-world scenarios. However, the limited types of operations supported by each HE scheme have been a major drawback in applications. While HE schemes
based on learning-with-error (LWE) problem provide efficient lookup table (LUT) evaluation in terms of latency, they have downsides in arithmetic operations and low throughput compared to HE schemes based on ring LWE (RLWE) problem. The use of HE on
circuits containing LUT has been partly limited if they contain arithmetic operations or their computational width is large.

In this paper, we propose homomorphic algorithms for batched queries on LUTs by using RLWE-based HE schemes. To look up encrypted LUTs of size $n$ on encrypted queries, our algorithms use $O(\log{n})$ homomorphic comparisons and $O(n)$ multiplications.
For unencrypted LUTs, our algorithms use $O(\log{n})$ comparisons, $O(\sqrt{n})$ ciphertext multiplications, and $O(n)$ scalar multiplications.

We provide a proof-of-concept implementation based on CKKS scheme (Asiacrypt 2017). The amortized running time for an encrypted (Resp. unencrypted) LUT of size $512$ is $0.041$ (Resp. $0.025$) seconds. Our implementation reported roughly $2.4$-$6.0$x
higher throughput than the current implementation of LWE-based schemes, with more flexibility on the structure of the LUTs.



## 2024/88

* Title: Enabling PERK on Resource-Constrained Devices
* Authors: Slim Bettaieb, Loïc Bidoux, Alessandro Budroni, Marco Palumbi, Lucas Pandolfo Perin
* [Permalink](https://eprint.iacr.org/2024/088)
* [Download](https://eprint.iacr.org/2024/088.pdf)

### Abstract

PERK is a digital signature scheme submitted to the recent NIST Post-Quantum Cryptography Standardization Process for Additional Digital Signature Schemes. For NIST security level I, PERK features sizes ranging from 6kB to 8.5kB, encompassing both the
signature and public key, depending on the parameter set.
Given its inherent characteristics, PERK's signing and verification algorithms involve the computation of numerous large objects, resulting in substantial stack-memory consumption ranging from 300kB to 1.5MB for NIST security level I and from 1.1MB to 5.
7MB for NIST security level V.
In this paper, we present a memory-versus-performance trade-off strategy that significantly reduces PERK's memory consumption to a maximum of approximately 82kB for any security level, enabling PERK to be executed on resource-constrained devices.
Additionally, we explore various optimizations tailored to the Cortex M4 and introduce the first implementation of PERK designed for this platform.



## 2024/89

* Title: Two-party GOST in two parts: fruitless search and fruitful synthesis
* Authors: Liliya Akhmetzyanova, Evgeny Alekseev, Alexandra Babueva, Lidiia Nikiforova, Stanislav Smyshlyaev
* [Permalink](https://eprint.iacr.org/2024/089)
* [Download](https://eprint.iacr.org/2024/089.pdf)

### Abstract

In the current paper we investigate the possibility of designing secure two-party signature scheme with the same verification algorithm as in the Russian standardized scheme (GOST scheme). We solve this problem in two parts. The first part is a (
fruitless) search for an appropriate scheme in the literature. It turned out that all existing schemes are insecure in the strong security models. The second part is a synthesis of new signature scheme and ends fruitfully. We synthesize a new two-party
GOST signature scheme, additionally using the commitment scheme, guided by the features of the GOST signature scheme, as well as the known attacks on existing schemes. We prove that this scheme is secure in a bijective random oracle model in the case
when one of the parties is malicious under the assumption that the classical GOST scheme is unforgeable in a bijective random oracle model and the commitment scheme is modelled as a random oracle.

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