[continued from previous message]

In this note we show how, given oracle access to $f : \{0,1\}^m \to \mathbb{F}$ and a point $z \in \mathbb{F}^m$, to compute $\hat{f}(z)$ using $O(2^m)$ field operations and only $O(m)$ space. This improves on a previous algorithm due to Vu et al. (
SP, 2013), which similarly uses $O(2^m)$ field operations but requires $O(2^m)$ space. Furthermore, the number of field additions in our algorithm is about half of that in Vu et al.'s algorithm, whereas the number of multiplications is the same up to
small additive terms.



## 2024/1104

* Title: Structural Lower Bounds on Black-Box Constructions of Pseudorandom Functions
* Authors: Amos Beimel, Tal Malkin, Noam Mazor
* [Permalink](https://eprint.iacr.org/2024/1104)
* [Download](https://eprint.iacr.org/2024/1104.pdf)

### Abstract

We address the black-box complexity of constructing pseudorandom functions (PRF) from pseudorandom generators (PRG). The celebrated GGM construction of Goldreich, Goldwasser, and Micali (Crypto 1984) provides such a construction, which (even when
combined with Levin's domain-extension trick) has super-logarithmic depth. Despite many years and much effort, this remains essentially the best construction we have to date. On the negative side, one step is provided by the work of Miles and Viola (TCC
2011), which shows that a black-box construction which just calls the PRG once and outputs one of its output bits, cannot be a PRF.

In this work, we make significant further progress: we rule out black-box constructions of PRF from PRG that follow certain structural constraints, but may call the PRG adaptively polynomially many times. In particular, we define ``tree constructions"
which generalize the GGM structure: they apply the PRG $G$ along a tree path, but allow for different choices of functions to compute the children of a node on the tree and to compute the next node on the computation path down the tree. We prove that a
tree construction of logarithmic depth cannot be a PRF (while GGM is a tree construction of super-logarithmic depth). We also show several other results and discuss the special case of one-call constructions.

Our main results in fact rule out even weak PRF constructions with one output bit. We use the oracle separation methodology introduced by Gertner, Malkin, and Reingold (FOCS 2001), and show that for any candidate black-box construction $F^G$ from $G$,
there exists an oracle relative to which $G$ is a PRG, but $F^G$ is not a PRF.



## 2024/1105

* Title: A New CRT-based Fully Homomorphic Encryption
* Authors: Anil Kumar Pradhan
* [Permalink](https://eprint.iacr.org/2024/1105)
* [Download](https://eprint.iacr.org/2024/1105.pdf)

### Abstract

We have proposed a novel FHE scheme that uniquely encodes the plaintext with noise in a way that prevents the increasing noise from overflowing and corrupting the plaintext. This allows users to perform computations on encrypted data smoothly. The scheme
is constructed using the Chinese Remainder Theorem (CRT), supporting a predefined number of modular operations on encrypted plaintext without the need for bootstrapping.
Although FHE recently became popular after Gentry's work and various developments have occurred in the last decade, the idea of "Fully Homomorphic Encryption (FHE)" scheme was first introduced in the 1970s by Rivest. The Chinese Remainder Theorem is one
of the most suitable tools for developing a FHE Scheme because it forms a ring homomorphism \( Z_{p_1} \times Z_{p_2} \times \ldots \times Z_{p_k} \cong Z_{p_1 p_2 \ldots p_k} \).
Various attempts have been made to develop a FHE using CRT, but most of them were unsuccessful, mainly due to the chosen plaintext attack (CPA).
The proposed scheme overcomes the chosen plaintext attack. The scheme also adds random errors to the message during encryption. However, these errors are added in such a way that, when homomorphic operations are performed over encrypted data, the
increasing values of errors never overwrite the values of the messages, as happens in LWE-based homomorphic schemes. Therefore, one can perform a predefined number of homomorphic operations (both addition and multiplication) without worrying about the
increasing values of errors.



## 2024/1106

* Title: Masked Vector Sampling for HQC
* Authors: Maxime Spyropoulos, David Vigilant, Fabrice Perion, Renaud Pacalet, Laurent Sauvage
* [Permalink](https://eprint.iacr.org/2024/1106)
* [Download](https://eprint.iacr.org/2024/1106.pdf)

### Abstract

Anticipating the advent of large quantum computers, NIST started a worldwide competition in 2016 aiming to define the next cryptographic standards. HQC is one of these post-quantum schemes still in contention, with four others already in the process of
being standardized. In 2022, Guo et al. introduced a timing attack that exploited an inconsistency in HQC rejection sampling function to recover its secret key in 866,000 calls to an oracle. The authors of HQC updated its specification by applying an
algorithm to sample vectors in constant time. A masked implementation of this function was then proposed for BIKE but it is not directly applicable to HQC. In this paper we propose a masked specification-compliant version of HQC vector sampling function
which relies, to our knowledge, on the first masked implementation of the Barrett reduction.



## 2024/1107

* Title: Phase Modulation Side Channels: Jittery JTAG for On-Chip Voltage Measurements
* Authors: Colin O'Flynn
* [Permalink](https://eprint.iacr.org/2024/1107)
* [Download](https://eprint.iacr.org/2024/1107.pdf)

### Abstract

Measuring the fluctuations of the clock phase of a target was identified as a leakage source on early electromagnetic side-channel investigations. Despite this, only recently was directly measuring the clock phase (or jitter) of digital signals from a
target connected to being a source of exploitable leakage. As the phase of a clock output will be related to signal propagation delay through the target, and this propagation delay is related to voltage, this means that most digital devices perform an
unintended phase modulation (PM) of their internal voltage onto clock output phases.

This paper first demonstrates an unprofiled CPA attack against a Cortex-M microcontroller using the phase of a clock output, observing the signal on both optically isolated and capacitively isolated paths. The unprofiled attack takes only 2-4x more
traces than an attack using a classic shunt-resistor measurement.

It is then demonstrated how the JTAG bypass mode can be used to force a clock through a digital device. This forced clock signal can then be used as a highly effective oscilloscope that is located on the target device. As the attack does not require
modifications to the device (such as capacitor removal or heat spreader removal) it is difficult to detect using existing countermeasures. The example attack over JTAG uses an unprofiled CPA attack, requiring only about 5x more traces than an ideal shunt-
resistor based measurement. In addition, a version of this attack using a fault correlation analysis attack is also demonstrated.

Countermeasures are discussed, and a simple resampling countermeasure is tested. All tools both offensive and defensive presented in the paper have been released under open-source licenses.



## 2024/1108

* Title: Faster Asynchronous Blockchain Consensus and MVBA
* Authors: Matthieu Rambaud
* [Permalink](https://eprint.iacr.org/2024/1108)
* [Download](https://eprint.iacr.org/2024/1108.pdf)

### Abstract

Blockchain consensus, a.k.a. BFT SMR, are protocols enabling $n$ processes to decide on an ever-growing chain. The fastest known asynchronous one is called 2-chain VABA (PODC'21 and FC'22), and is used as fallback chain in Abraxas* (CCS'23). It has a
claimed $9.5\delta$ expected latency when used for a single shot instance, a.k.a. an MVBA.
We exhibit attacks breaking it. Hence, the title of the fastest asynchronous MVBA with quadratic messages complexity goes to sMVBA (CCS'22), with $10\delta$ expected latency.
Our positive contributions are two new and complementary designs.

$\bullet$ 2PAC (2-phase asynchronous consensus). It has a simpler and lighter chaining than in previous approaches. Instantiated with either quadratic or cubic phases of voting, it yields:

2PAC$^\text{lean}$: $+90\%$ throughput and $9.5\delta$ expected latency, with quadratic ($O(n^2)$) messages complexity. In both 2-chain VABA and sMVBA (as if chained, with pipelining), the quorum-certified transactions which were produced in the worst-
case 1/3 of views with a slow leader were dumped, so the work was lost. The simpler design of 2PAC inserts such blocks in straight-line in the chain.
Thus, contrary to naive uncle-referencing, this comes with no computational overhead, yielding a net $+50\%$ throughput gain over chained sMVBA. Both the remaining throughput and latency ($-0.5\delta$) gains, come from the lighter interactive
construction of proofs of consistency appended to proposed blocks, compared to sMVBA.

2PAC$^\text{BIG}$: the fastest asynchronous blockchain consensus with cubic ($O(n^3)$) messages complexity. Fault-free single shot MVBA runs decide in just $4\delta$, as soon as no message is delivered more than twice faster than others: GradedDAG (
SRDS'23) required furthermore no messages reordering.

$\bullet$ Super Fast Pipelined Blocks. This is an upgrade of previous approaches for pipelining: in 2-chain VABA, Cordial Miners (DISC'23) and GradedDAG, a block pipelined by a leader in the middle of the view had almost twice larger latency than the
non-pipelined block. Our design provides a fast path deciding the pipelined block with even smaller latency than the non-pipelined block. The fast delay is guaranteed in all executions with a fair scheduler, but remarkably, whatever the behaviors of
faulty processes. Consistency is preserved by a lightweight mechanism, of one threshold signature appended per proposal.
Instantiated with the previous protocols, it yields: s2PAC$^\text{lean}$, with fast decision of pipelined blocks in $4\delta$; s2PAC$^\text{BIG}$, in $3\delta$; and sGradedDAG, in $3\delta$.

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