## In this issue

1. [2022/1516] Obfuscation of Evasive Algebraic Set Membership
2. [2024/482] Single Server PIR via Homomorphic Thorp Shuffles
3. [2024/483] Lower data attacks on Advanced Encryption Standard
4. [2024/484] Harmonizing PUFs for Forward Secure Authenticated ...
5. [2024/485] A Variation on Knellwolf and Meier's Attack on the ...
6. [2024/486] Anamorphic Encryption: New Constructions and ...
7. [2024/487] Real-Valued Somewhat-Pseudorandom Unitaries
8. [2024/488] Improving Generic Attacks Using Exceptional Functions
9. [2024/489] Guess and Determine Analysis Based on Set Split
10. [2024/490] One Tree to Rule Them All: Optimizing GGM Trees and ...
11. [2024/491] Updatable Policy-Compliant Signatures
12. [2024/492] Statistical testing of random number generators and ...

## 2022/1516

* Title: Obfuscation of Evasive Algebraic Set Membership
* Authors: Steven D. Galbraith, Trey Li
* [Permalink](https://eprint.iacr.org/2022/1516)
* [Download](https://eprint.iacr.org/2022/1516.pdf)

### Abstract

We define the membership function of a set as the function that determines whether an input is an element of the set. Canetti, Rothblum, and Varia showed how to obfuscate evasive membership functions of hyperplanes over a finite field of order an exponentially large prime, assuming the hardness of a modified decisional Diffie-Hellman problem. Barak, Bitansky, Canetti, Kalai, Paneth, and Sahai extended their work from hyperplanes to hypersurfaces of bounded degree, assuming multilinear maps. Both works are limited to algebraic sets over large fields of prime orders, and are based on less standard assumptions, although they prove virtual black-box security.

In this paper, we handle much more general algebraic sets based on more standard assumptions, and prove input-hiding security, which is not weaker nor stronger than virtual black-box security (i.e., they are incomparable). Our first obfuscator handles affine algebraic sets over finite fields of order an arbitrary prime power. It is based on the preimage-resistance property of cryptographic hash function families. Our second obfuscator applies to both affine and projective algebraic sets over finite fields of order a polynomial size prime power. It is based on the same hardness assumption(s) required by input-hiding small superset obfuscation. Our paper is the first to handle the obfuscation problem of projective algebraic sets over small finite fields.

## 2024/482

* Title: Single Server PIR via Homomorphic Thorp Shuffles
* Authors: Ben Fisch, Arthur Lazzaretti, Zeyu Liu, Charalampos Papamanthou
* [Permalink](https://eprint.iacr.org/2024/482)
* [Download](https://eprint.iacr.org/2024/482.pdf)

### Abstract

Private Information Retrieval (PIR) is a two player protocol where the client, given some query $x \in [N]$ interacts with the server, which holds a $N$-bit string $\textsf{DB}$ in order to privately retrieve $\textsf{DB}[x]$. In this work, we focus on the single server client-preprocessing model, initially idealized by Corrigan-Gibbs and Kogan (EUROCRYPT 2020), where the client and server first run some joint preprocessing algorithm, after which the client can retrieve elements of the server's string $\textsf{DB}$ privately in time sublinear in $N$.

All known constructions of single server client-preprocessing PIR rely on one of the following two paradigms: (1) a linear-bandwidth offline phase where the client downloads the whole database from the server, or (2) a sublinear-bandwidth offline phase where however the server has to compute a large-depth ($O_\lambda (N)$) circuit under FHE in order to execute the preprocessing phase.

In this paper, we construct a single server client-preprocessing PIR scheme which achieves both sublinear offline bandwidth (the client does not have to download the whole database offline) and a low-depth (i.e. $O_\lambda(1)$), highly parallelizable preprocessing circuit. We estimate that on a single thread, our scheme's preprocessing time should be more than 350x times faster than in prior single server client-preprocessing PIR constructions. Moreover, with parallelization, the latency reduction would be even more drastic. In addition, this construction also allows for updates in $O_\lambda (1)$ time, something not achieved before in this model.

## 2024/483

* Title: Lower data attacks on Advanced Encryption Standard
* Authors: Orhun Kara
* [Permalink](https://eprint.iacr.org/2024/483)
* [Download](https://eprint.iacr.org/2024/483.pdf)

### Abstract

The Advanced Encryption Standard (AES) is one of the most commonly used and analyzed encryption algorithms. In this work, we present new combinations of some prominent attacks on AES, achieving new records in data requirements among attacks, utilizing only $2^4$ and $2^{16}$ chosen plaintexts (CP) for 6-round and 7-round AES-192/256 respectively. One of our attacks is a combination of a meet-in-the-middle (MiTM) attack with a square attack mounted on 6-round AES-192/256 while another attack combines an MiTM attack and an integral attack, utilizing key space partitioning technique, on 7-round AES-192/256. Moreover, we illustrate that impossible differential (ID) attacks can be viewed as the dual of MiTM attacks in certain aspects which enables us to recover the correct key using the meet-in-the-middle (MiTM) technique instead of sieving through all potential wrong keys in our ID attack. Furthermore, we introduce the constant guessing technique in the inner rounds which significantly reduces the number of key bytes to be searched. The time and memory complexities of our attacks remain marginal.

## 2024/484

* Title: Harmonizing PUFs for Forward Secure Authenticated Key Exchange with Symmetric Primitives
* Authors: Harishma Boyapally, Durba Chatterjee, Kuheli Pratihar, Sayandeep Saha, Debdeep Mukhopadhyay, Shivam Bhasin
* [Permalink](https://eprint.iacr.org/2024/484)
* [Download](https://eprint.iacr.org/2024/484.pdf)

### Abstract

Physically Unclonable Functions (PUFs) have been a potent choice for enabling low-cost, secure communication. However, in most applications, one party holds the PUF, and the other securely stores the challenge-response pairs (CRPs)..
It does not remove the need for secure storage entirely, which is one of the goals of PUFs.
This paper proposes a PUF-based construction called Harmonizing PUFs ($\textsf{H_PUF}$s), allowing two independent PUFs to generate the same outcome without storing any confidential data.
As an application of $\textsf{H_PUF}$ construction, we present $\textsf{H-AKE}$: a low-cost authenticated key exchange protocol for resource-constrained nodes that is secure against replay and impersonation attacks. The novelty of the protocol is that it achieves forward secrecy without requiring to perform asymmetric group operations like elliptic curve scalar multiplications underlying traditional key-exchange techniques.

## 2024/485

* Title: A Variation on Knellwolf and Meier's Attack on the Knapsack Generator
* Authors: Florette Martinez
* [Permalink](https://eprint.iacr.org/2024/485)
* [Download](https://eprint.iacr.org/2024/485.pdf)

### Abstract

Pseudo-random generators are deterministic algorithms that take in input a random secret seed and output a flow of random-looking numbers. The Knapsack generator, presented by Rueppel and Massey in 1985 is one of the many attempt at designing a pseudo-random generator that is cryptographically secure. It is based on the subset-sum problem, a variant of the Knapsack optimization problem, which is considered computationally hard.

In 2011 Simon Knellwolf et Willi Meier found a way to go around this hard problem and exhibited a weakness of this generator. In addition to be able to distinguish the outputs from the uniform distribution, they designed an algorithm that retrieves a large portion of the secret. We present here an alternate version of the attack, with similar costs, that works on the same range of parameters but retrieves a larger portion of the secret.

## 2024/486

* Title: Anamorphic Encryption: New Constructions and Homomorphic Realizations
* Authors: Dario Catalano, Emanuele Giunta, Francesco Migliaro
* [Permalink](https://eprint.iacr.org/2024/486)
* [Download](https://eprint.iacr.org/2024/486.pdf)

### Abstract

The elegant paradigm of Anamorphic Encryption (Persiano et al., Eurocrypt 2022) considers the question of establishing a private communication in a world controlled by a dictator.
The challenge is to allow two users, sharing some secret anamorphic key, to exchange covert messages without the dictator noticing, even when the latter has full access to the regular secret keys.
Over the last year several works considered this question and proposed constructions, novel extensions and strengthened definitions.

In this work we make progress on the study of this primitive in three main directions. First, we show that two general and well established encryption paradigms, namely hybrid encryption and the IBE-to-CCA transform, admit very simple and natural anamorphic extensions. Next, we show that anamorphism, far from being a phenomenon isolated to "basic" encryption schemes, extends also to homomorphic encryption. We show that some existing homomorphic schemes, (and most notably the fully homomorphic one by Gentry, Sahai and Waters) can be made anamorphic, while retaining their homomorphic properties both with respect to the regular and the covert message.

Finally we refine the notion of anamorphic encryption by envisioning the possibility of splitting the anamorphic key into an encryption component (that only allows to encrypt covert messages) and a decryption component. This makes possible for a receiver to set up several, independent, covert channels associated with a single covert key.