[continued from previous message]
* Authors: Camille Nuoskala, Hossein Abdinasibfar, Antonis Michalas
* [Permalink](
https://eprint.iacr.org/2024/1387)
* [Download](
https://eprint.iacr.org/2024/1387.pdf)
### Abstract
Functional Encryption (FE) is a cryptographic technique established to guarantee data privacy while allowing the retrieval of specific results from the data.
While traditional decryption methods rely on a secret key disclosing all the data, FE introduces a more subtle approach. The key generation algorithm generates function-specific decryption keys that can be adaptively provided based on policies. Adaptive
access control is a good feature for privacy-preserving techniques. Generic schemes have been designed to run basic functions, such as linear regression. However, they often provide a narrow set of outputs, resulting in a lack of thorough analysis. The
bottom line is that despite significant research, FE still requires appropriate constructions to unleash its full potential in securely analyzing data and providing more insights. In this article, we introduce SPADE, a novel FE scheme that features
multiple users and offers fine-grained access control through partial decryption of the ciphertexts. Unlike existing FE schemes, our construction also supports qualitative data, such as genomics, expanding the applications of privacy-preserving analysis
to enable a comprehensive study of the data. SPADE is a significant advancement that balances privacy and data analysis with clear implications in healthcare and finance.
To verify its applicability, we conducted extensive experiments on datasets used in sleep medicine (hypnogram data) and DNA analysis (genomic records).
## 2024/1388
* Title: One-Way Functions and pKt Complexity
* Authors: Shuichi Hirahara, Zhenjian Lu, Igor C. Oliveira
* [Permalink](
https://eprint.iacr.org/2024/1388)
* [Download](
https://eprint.iacr.org/2024/1388.pdf)
### Abstract
We introduce $\mathsf{pKt}$ complexity, a new notion of time-bounded Kolmogorov complexity that can be seen as a probabilistic analogue of Levin's $\mathsf{Kt}$ complexity. Using $\mathsf{pKt}$ complexity, we upgrade two recent frameworks that
characterize one-way functions ($\mathsf{OWF}$) via symmetry of information and meta-complexity, respectively. Among other contributions, we establish the following results:
- $\mathsf{OWF}$ can be based on the worst-case assumption that $\mathsf{BPEXP}$ is not contained infinitely often in $\mathsf{P}/\mathsf{poly}$ if the failure of symmetry of information for $\mathsf{pKt}$ in the $\textit{worst-case}$ implies its
failure on $\textit{average}$.
- (Infinitely-often) $\mathsf{OWF}$ exist if and only if the average-case easiness of approximating $\mathsf{pKt}$ with $\textit{two-sided}$ error implies its (mild) average-case easiness with $\textit{one-sided}$ error.
Previously, in a celebrated result, Liu and Pass (CRYPTO 2021 and CACM 2023) proved that one can base (infinitely-often) $\mathsf{OWF}$ on the assumption that $\mathsf{EXP} \nsubseteq \mathsf{BPP}$ if and only if there is a reduction from computing $\
mathsf{Kt}$ on average with $\textit{zero}$ error to computing $\mathsf{Kt}$ on average with $\textit{two-sided}$ error. In contrast, our second result shows that closing the gap between two-sided error and one-sided error average-case algorithms for
approximating $\mathsf{pKt}$ is both necessary and sufficient to $\textit{unconditionally}$ establish the existence of $\mathsf{OWF}$.
## 2024/1389
* Title: DL-SITM: Deep Learning-Based See-in-the-Middle Attack on AES
* Authors: Tomáš Gerlich, Jakub Breier, Pavel Sikora, Zdeněk Martinásek, Aron Gohr, Anubhab Baksi, Xiaolu Hou
* [Permalink](
https://eprint.iacr.org/2024/1389)
* [Download](
https://eprint.iacr.org/2024/1389.pdf)
### Abstract
The see-in-the-middle (SITM) attack combines differential cryptanalysis and the ability to observe differential patterns in the side-channel leakage traces to reveal the secret key of SPN-based ciphers. While SITM presents a fresh perspective to side-
channel analysis and allows attacks on deeper cipher rounds, there are practical difficulties that come with this method. First, one must realize a visual inspection of millions of power traces. Second, there is a strong requirement to reduce noise to a
minimum, achieved by averaging over 1000 traces in the original work, to see the patterns. Third, the presence of a jitter-based countermeasure greatly affects pattern identification, making the visual inspection infeasible. In this paper we aim to
tackle these difficulties by using a machine learning approach denoted as DL-SITM (deep learning SITM). The fundamental idea of our approach is that, while a collision obscured by noise is imperceptible in a manual inspection, a powerful deep learning
model can identify it, even when a jitter-based countermeasure is in place. As we show with a practical experiment, the proposed DL-SITM approach can distinguish the two valid differentials from over 4M differential traces with only six false positives.
Extrapolating from the parameters of this experiment, we get a rough estimate of $2^{43}$ key candidates for the post-processing step of our attack, which places it easily in the practical range. At the same time, we show that even with a jitter
countermeasure shifting the execution by $\pm15$ samples, the testing f1-score stays at a relatively high (0.974).
## 2024/1390
* Title: Cache Timing Leakages in Zero-Knowledge Protocols
* Authors: Shibam Mukherjee, Christian Rechberger, Markus Schofnegger
* [Permalink](
https://eprint.iacr.org/2024/1390)
* [Download](
https://eprint.iacr.org/2024/1390.pdf)
### Abstract
The area of modern zero-knowledge proof systems has seen a significant rise in popularity over the last couple of years, with new techniques and optimized constructions emerging on a regular basis.
As the field matures, the aspect of implementation attacks becomes more relevant, however side-channel attacks on zero-knowledge proof systems have seen surprisingly little treatment so far. In this paper we give an overview of potential attack vectors
and show that some of the underlying finite field libraries, and implementations of heavily used components like hash functions, are vulnerable w.r.t. cache attacks on CPUs.
On the positive side, we demonstrate that the computational overhead to protect against these attacks is relatively small.
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)