[digest] 2024 Week 13

## 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.



## 2024/487

* Title: Real-Valued Somewhat-Pseudorandom Unitaries
* Authors: Zvika Brakerski, Nir Magrafta
* [Permalink](https://eprint.iacr.org/2024/487)
* [Download](https://eprint.iacr.org/2024/487.pdf)

### Abstract

We explore a very simple distribution of unitaries: random (binary) phase -- Hadamard -- random (binary) phase -- random computational-basis permutation.
We show that this distribution is statistically indistinguishable from random Haar unitaries for any polynomial set of orthogonal input states (in any basis) with polynomial multiplicity.
This shows that even though real-valued unitaries cannot be completely pseudorandom (Haug, Bharti, Koh, arXiv:2306.11677), we can still obtain some pseudorandom properties without giving up on the simplicity of a real-valued unitary.

Our analysis shows that an even simpler construction: applying a random (binary) phase followed by a random computational-basis permutation, would suffice, assuming that the input is orthogonal and flat (that is, has high min-entropy when measured in the computational basis).

Using quantum-secure one-way functions (which imply quantum-secure pseudorandom functions and permutations), we obtain an efficient cryptographic instantiation of the above.



## 2024/488

* Title: Improving Generic Attacks Using Exceptional Functions
* Authors: Xavier Bonnetain, Rachelle Heim Boissier, Gaëtan Leurent, André Schrottenloher
* [Permalink](https://eprint.iacr.org/2024/488)
* [Download](https://eprint.iacr.org/2024/488.pdf)

### Abstract

Over the past ten years, the statistical properties of random functions have been particularly fruitful for generic attacks. Initially, these attacks targeted iterated hash constructions and their combiners, developing a wide array of methods based on internal collisions and on the average behavior of iterated random functions. More recently, Gilbert et al. (EUROCRYPT 2023) introduced a forgery attack on so-called duplex-based Authenticated Encryption modes which was based on exceptional random functions, i.e., functions whose graph admits a large component with an exceptionally small cycle.
In this paper, we expand the use of such functions in generic cryptanalysis with several new attacks. First, we improve the attack of Gilbert et al. from O(2^3c/4) to O(2^2c/3), where c is the capacity. This new attack uses a nested pair of functions with exceptional behavior, where the second function is defined over the cycle of the first one. Next, we introduce several new generic attacks against hash combiners, notably using small cycles to improve the complexities of the best existing attacks on the XOR combiner, Zipper Hash and Hash-Twice.
Last but not least, we propose the first quantum second preimage attack against Hash-Twice, reaching a quantum complexity O(2^3n/7).



## 2024/489

* Title: Guess and Determine Analysis Based on Set Split
* Authors: Zhe CEN, Xiutao FENG, Zhangyi WANG, Yamin ZHU, Chunping CAO
* [Permalink](https://eprint.iacr.org/2024/489)
* [Download](https://eprint.iacr.org/2024/489.pdf)

### Abstract

The guess and determine attack is a common method in cryptanalysis. Its idea is to firstly find some variables which can deduced all remaining variables in a cipher and then traverse all values of these variables to find a solution.. People usually utilize the exhausted search to find these variables. However, it is not applicable any more when the number of variables is a bit large. In this work we propose a guess and determine analysis based on set split to find as few variables as possible in the first step of guess and determine attack, which is a kind of exhausted search based on trading space for time and is more effective than the latter.
Firstly we give an idea of set split in detail by introducing some conceptions such as base set, likely solution region and so on. And then we discuss how to utilize the set split to achieve a guess and determine analysis and give its specific implementation scheme. Finally, comparing it with the other two guess and determine analysis based on the exhausted search and the MILP method, we illustrate the effectiveness of our method by two ciphers Snow 2.0 and Enocoro-128v2. Our method spends about 0.000103 seconds finding a best solution of 9 variables for the former and 0.13 seconds finding a best solution of 18 variables for the latter in a personal Macbook respectively, which are better than those of both the exhausted search and the MILP method.



## 2024/490

* Title: One Tree to Rule Them All: Optimizing GGM Trees and OWFs for Post-Quantum Signatures
* Authors: Carsten Baum, Ward Beullens, Shibam Mukherjee, Emmanuela Orsini, Sebastian Ramacher, Christian Rechberger, Lawrence Roy, Peter Scholl
* [Permalink](https://eprint.iacr.org/2024/490)
* [Download](https://eprint.iacr.org/2024/490.pdf)

### Abstract

The use of MPC-in-the-Head (MPCitH)-based zero-knowledge proofs of knowledge (ZKPoK) to prove knowledge of a preimage of a one-way function (OWF) is a popular approach towards constructing efficient post-quantum digital signatures. Starting with the Picnic signature scheme, many optimized MPCitH signatures using a variety of (candidate) OWFs have been proposed. Recently, Baum et al. (CRYPTO 2023) showed a fundamental improvement to MPCitH, called VOLE-in-the-Head (VOLEitH), which can generically reduce the signature size by at least a factor of two without decreasing computational performance or introducing new assumptions. Based on this, they designed the FAEST signature which uses AES as the underlying OWF. However, in comparison to MPCitH, the behavior of VOLEitH when using other OWFs is still unexplored.

In this work, we improve a crucial building block of the VOLEitH and MPCitH approaches, the so-called all-but-one vector commitment, thus decreasing the signature size of VOLEitH and MPCitH signature schemes. Moreover, by introducing a small Proof of Work into the signing procedure, we can improve the parameters of VOLEitH (further decreasing signature size) without compromising the computational performance of the scheme.
Based on these optimizations, we propose three VOLEitH signature schemes FAESTER, KuMQuat, and MandaRain based on AES, MQ, and Rain, respectively. We carefully explore the parameter space for these schemes and implement each, showcasing their performance with benchmarks. Our experiments show that these three signature schemes outperform MPCitH-based competitors that use comparable OWFs, in terms of both signature size and signing/verification time.



## 2024/491

* Title: Updatable Policy-Compliant Signatures
* Authors: Christian Badertscher, Monosij Maitra, Christian Matt, Hendrik Waldner
* [Permalink](https://eprint.iacr.org/2024/491)
* [Download](https://eprint.iacr.org/2024/491.pdf)

### Abstract

Policy-compliant signatures (PCS) are a recently introduced primitive by Badertscher et
al. [TCC 2021] in which a central authority distributes secret and public keys associated with sets of attributes (e.g., nationality, affiliation with a specific department, or age) to its users. The authority also enforces a policy determining which senders can sign messages for which receivers based on a joint check of their attributes. For example, senders and receivers must have the same nationality, or only senders that are at least 18 years old can send to members of the computer science department. PCS further requires attribute-privacy – nothing about the users’ attributes is revealed from their public keys and signatures apart from whether the attributes satisfy the policy or not. The policy in a PCS scheme is fixed once and for all during the setup. Therefore, a policy update requires a redistribution of all keys. This severely limits the practicality of PCS. In this work, we introduce the notion of updatable policy-compliant signatures (UPCS) extending PCS with a mechanism to efficiently update the policy without redistributing keys to all participants.
We define the notion of UPCS and provide the corresponding security definitions. We then provide a generic construction of UPCS based on digital signatures, a NIZK proof system, and a so-called secret-key two-input partially-hiding predicate encryption (2-PHPE) scheme. Unfortunately, the only known way to build the latter for general two-input predicates is using indistinguishability obfuscation. We show that the reliance on the heavy tool of 2-PHPE is inherent to build UPCS by proving that non-interactive UPCS implies 2-PHPE.
To circumvent the reliance on 2-PHPE, we consider interactive UPCS, which allows the sender and receiver to interact during the message signing procedure. In this setting, we present two schemes: the first one requires only a digital signature scheme, a NIZK proof system, and secure two-party computation. This scheme works for arbitrary policies, but requires sender and receiver to engage in a two-party computation protocol for each policy update. Our second scheme additionally requires a (single-input) predicate-encryption scheme but, in turn, only requires a single interaction between sender and receiver, independent of the updates. In contrast to 2-PHPE, single-input predicate encryption for certain predicate classes is known to exist (e.g., from pairings) under more concrete and well-understood assumptions.



## 2024/492

* Title: Statistical testing of random number generators and their improvement using randomness extraction
* Authors: Cameron Foreman, Richie Yeung, Florian J. Curchod
* [Permalink](https://eprint.iacr.org/2024/492)
* [Download](https://eprint.iacr.org/2024/492.pdf)

### Abstract

Random number generators (RNGs) are notoriously hard to build and test, especially in a cryptographic setting. Although one cannot conclusively determine the quality of an RNG by testing the statistical properties of its output alone, running numerical tests is both a powerful verification tool and the only universally applicable method. In this work, we present and make available a comprehensive statistical testing environment (STE) that is based on existing statistical test suites. The STE can be parameterised to run lightweight (i..e. fast) all the way to intensive testing, which goes far beyond what is required by certification bodies. With it, we benchmark the statistical properties of several RNGs, comparing them against each other. We then present and implement a variety of post-processing methods, in the form of randomness extractors, which improve the RNG's output quality under different sets of assumptions and analyse their impact through numerical testing with the STE.