[continued from previous message]

* Title: Powerformer: Efficient Privacy-Preserving Transformer with Batch Rectifier-Power Max Function and Optimized Homomorphic Attention
* Authors: Dongjin Park, Eunsang Lee, Joon-Woo Lee
* [Permalink](https://eprint.iacr.org/2024/1429)
* [Download](https://eprint.iacr.org/2024/1429.pdf)

### Abstract

We propose an efficient non-interactive privacy-preserving Transformer inference architecture called Powerformer. Since softmax is a non-algebraic operation, previous studies have attempted to modify it to be HE-friendly, but these methods have
encountered issues with accuracy degradation or prolonged execution times due to the use of multiple bootstrappings. We propose replacing softmax with a new ReLU-based function called the \textit{Batch Rectifier-Power max} (BRPmax) function without any
unstable approximation methods, which outperforms even original BERT performance within BERT-Large model while requiring fewer levels, allowing it to operate with only a single bootstrapping. We also present a matrix multiplication algorithms specialized
for attention block that reduce the number of key-switchings by 35% to 91% compared to existing state-of-the-art methods. We design clear end-to-end HE-based implementation for private Transformer model, and our implementation of Powerformer on the BERT-
tiny model using RNS-CKKS takes 503 seconds on a single-threaded CPU, and to the best of our knowledge, this is the first end-to-end non-interactive Transformer implementation using HE.



## 2024/1430

* Title: MYao: Multiparty ``Yao'' Garbled Circuits with Row Reduction, Half Gates, and Efficient Online Computation
* Authors: Aner Ben-Efraim, Lior Breitman, Jonathan Bronshtein, Olga Nissenbaum, Eran Omri
* [Permalink](https://eprint.iacr.org/2024/1430)
* [Download](https://eprint.iacr.org/2024/1430.pdf)

### Abstract

Garbled circuits are a powerful and important cryptographic primitive, introduced by Yao [FOCS 1986] for secure two-party computation. Beaver, Micali and Rogaway (BMR) [STOCS 1990] extended the garbled circuit technique to construct the first constant-
round secure multiparty computation (MPC) protocol. In the BMR protocol, the garbled circuit size grows linearly and the online computation time grows quadratically with the number of parties. Previous solutions to avoid this relied on key-homomorphic
PRFs, incurring a large garbled circuit size and slow online computation time. We present MYao, a new multiparty protocol for achieving a ``Yao'' garbled circuit, i.e., the garbled circuit size and online computation time are independent of the number of parties. The key innovation is that the parties collaboratively compute the
PRF in MPC, which was previously believed to be inefficient. In this paper, we challenge this long-standing assumption by basing the garbled circuit construction on ``MPC-friendly'' PRFs. One of the highlights of our new technique is that we are able to
achieve, for the first time, full row-reduction in multiparty garbled circuits. To achieve this optimization without increasing the number of rounds, we utilize free-XOR and half gates, presenting a new technique for choosing the keys, based on a
naturally occurring relation between the 2 keys of the 2 half-gates.
MYao reduces the garbled circuit size by more than 90%, the total communication by more than 75%, and the online computation time by more than 10%, compared to all known solutions based on key-homomorphic PRFs, thus substantially improving the overall
efficiency in both the offline and the online phases. Furthermore, MYao significantly improves over semi-honest BMR in online phase efficiency when the number of parties exceeds 80.



## 2024/1431

* Title: Interactive Line-Point Zero-Knowledge with Sublinear Communication and Linear Computation
* Authors: Fuchun Lin, Chaoping Xing, Yizhou Yao
* [Permalink](https://eprint.iacr.org/2024/1431)
* [Download](https://eprint.iacr.org/2024/1431.pdf)

### Abstract

Studies of vector oblivious linear evaluation (VOLE)-based zero-knowledge (ZK) protocols flourish in recent years. Such ZK protocols feature optimal prover computation and a flexibility for handling arithmetic circuits over arbitrary fields. However,
most of them have linear communication, which constitutes a bottleneck for handling large statements in a slow network. The pioneer work AntMan (CCS'22), achieved sublinear communication for the first time within VOLE-based ZK, but lost the advantage of
fast proving. In this work, we propose two new VOLE-based ZK constructions that achieve sublinear communication and linear computation, simultaneously. Let $\mathcal{C}$ be a circuit with size $S$, input size $n$, and depth $d$. In particular, our first
ZK, specialized for layered circuits, has communication $O(n+d\log{S})$, while our second ZK can be used to prove general circuits and has communication $O(n+d\log{S}+d^2)$.

Our results are obtained by introducing the powerful sum-check techniques from the mature line of works on interactive proofs into the context of VOLE-based ZK for the first time. Reminiscent of the non-interactive line-point zero-knowledge proof system (
ITC'21), we introduce an interactive line-point zero-knowledge (ILPZK) proof system, which closely connects with VOLE-based ZK protocols. In addition, our works also enrich the studies of ZK based on interactive proofs, with new interesting features (e.g.
, having information-theoretic UC-security, naturally supporting any field) achieved.



## 2024/1432

* Title: On Multi-user Security of Lattice-based Signature under Adaptive Corruptions and Key Leakages
* Authors: Masayuki Fukumitsu, Shingo Hasegawa
* [Permalink](https://eprint.iacr.org/2024/1432)
* [Download](https://eprint.iacr.org/2024/1432.pdf)

### Abstract

We consider the multi-user security under the adaptive corruptions and key leakages ($\rm{MU^{c\&l}}$ security) for lattice-based signatures. Although there exists an $\rm{MU^{c\&l}}$ secure signature based on a number-theoretic assumption, or a leakage-
resilient lattice-based signature in the single-user setting, $\rm{MU^{c\&l}}$ secure lattice-based signature is not known.

We examine the existing lattice-based signature schemes from the viewpoint of $\rm{MU^{c\&l}}$ security, and find that the security of the Lyubashevsky's signature, which is proven to have the ordinary single-user security only, can be extended to the
multi-user security even if we take the adaptive corruptions and the key leakages into account.

Our security proof in the multi-user setting makes use of the feature of the SIS problem so that a SIS instance is set to the public parameter and a reduction algorithm can set a public key with a secret key in order to answer a corruption query. We also
show that the entropy of the secret key is kept under the bounded leakage with a high probability and then the leakage resilience of signature holds.



## 2024/1433

* Title: $Shortcut$: Making MPC-based Collaborative Analytics Efficient on Dynamic Databases
* Authors: Peizhao Zhou, Xiaojie Guo, Pinzhi Chen, Tong Li, Siyi Lv, Zheli Liu * [Permalink](https://eprint.iacr.org/2024/1433)
* [Download](https://eprint.iacr.org/2024/1433.pdf)

### Abstract

Secure Multi-party Computation (MPC) provides a promising solution for privacy-preserving multi-source data analytics. However, existing MPC-based collaborative analytics systems (MCASs) have unsatisfying performance for scenarios with dynamic databases.
Naively running an MCAS on a dynamic database would lead to significant redundant costs and raise performance concerns, due to the substantial duplicate contents between the pre-updating and post-updating databases.

In this paper, we propose $Shortcut$, a framework that can work with MCASs to enable efficient queries on dynamic databases that support data insertion, deletion, and update. The core idea of $Shortcut$ is to materialize previous query results and
directly update them via our query result update (QRU) protocol to obtain current query results. We customize several efficient QRU protocols for common SQL operators, including Order-by-Limit, Group-by-Aggregate, Distinct, Join, Select, and Global
Aggregate. These protocols are composable to implement a wide range of query functions. In particular, we propose two constant-round protocols to support data insertion and deletion. These protocols can serve as important building blocks of other
protocols and are of independent interest. They address the problem of securely inserting/deleting a row into/from an ordered table while keeping the order. Our experiments show that $Shortcut$ outperforms naive MCASs for minor updates arriving in time,
which captures the need of many realistic applications (e.g., insurance services, account data management). For example, for a single query after an insertion, $Shortcut$ achieves up to $186.8 \times$ improvement over those naive MCASs without our QRU
protocols on a dynamic database with $2^{16} \sim 2^{20}$ rows, which is common in real-life applications.



## 2024/1434

* Title: Untangling the Security of Kilian's Protocol: Upper and Lower Bounds
* Authors: Alessandro Chiesa, Marcel Dall'Agnol, Ziyi Guan, Nicholas Spooner, Eylon Yogev
* [Permalink](https://eprint.iacr.org/2024/1434)
* [Download](https://eprint.iacr.org/2024/1434.pdf)

### Abstract

Sigma protocols are elegant cryptographic proofs that have become a cornerstone of modern cryptography. A notable example is Schnorr's protocol, a zero-knowledge proof-of-knowledge of a discrete logarithm. Despite extensive research, the security of
Schnorr's protocol in the standard model is not fully understood.

In this paper we study Kilian's protocol, an influential public-coin interactive protocol that, while not a sigma protocol, shares striking similarities with sigma protocols. The first example of a succinct argument, Kilian's protocol is proved secure
via rewinding, the same idea used to prove sigma protocols secure. In this paper we show how, similar to Schnorr's protocol, a precise understanding of the security of Kilian's protocol remains elusive. We contribute new insights via upper bounds and
lower bounds.
- Upper bounds. We establish the tightest known bounds on the security of Kilian's protocol in the standard model, via strict-time reductions and via expected-time reductions. Prior analyses are strict-time reductions that incur large overheads or
assume restrictive properties of the PCP underlying Kilian's protocol.
- Lower bounds. We prove that significantly improving on the bounds that we establish for Kilian's protocol would imply improving the security analysis of Schnorr's protocol beyond the current state-of-the-art (an open problem). This partly explains the
difficulties in obtaining tight bounds for Kilian's protocol.



## 2024/1435

* Title: Actively Secure Polynomial Evaluation from Shared Polynomial Encodings * Authors: Pascal Reisert, Marc Rivinius, Toomas Krips, Sebastian Hasler, Ralf Küsters
* [Permalink](https://eprint.iacr.org/2024/1435)
* [Download](https://eprint.iacr.org/2024/1435.pdf)

### Abstract

Many of the currently best actively secure Multi-Party Computation (MPC) protocols like SPDZ (Damgård et al., CRYPTO 2012) and improvements thereof use correlated randomness to speed up the time-critical online phase. Although many of these protocols
still rely on classical Beaver triples, recent results show that more complex correlations like matrix or convolution triples lead to more efficient evaluations of the corresponding operations, i.e. matrix multiplications or tensor convolutions. In this
paper, we address the evaluation of multivariate polynomials with a new form of randomness: polytuples. We use the polytuples to construct a new family of randomized encodings which then allow us to evaluate the given multivariate polynomial. Our
approach can be fine-tuned in various ways to the constraints of applications at hand, in terms of round complexity, bandwidth, and tuple size. We show that for many real-world setups, a polytuples-based online phase outperforms state-of-the-art
protocols based on Beaver triples.



## 2024/1436

* Title: Eva: Efficient IVC-Based Authentication of Lossy-Encoded Videos
* Authors: Chengru Zhang, Xiao Yang, David Oswald, Mark Ryan, Philipp Jovanovic * [Permalink](https://eprint.iacr.org/2024/1436)
* [Download](https://eprint.iacr.org/2024/1436.pdf)

### Abstract

With the increasing spread of fake videos for misinformation, proving the provenance of an edited video (without revealing the original one) becomes critical. To this end, we introduce Eva, the first cryptographic protocol for authenticating lossy-
encoded videos. Compared to previous cryptographic methods for image authentication, Eva supports significantly larger amounts of data that undergo complex transformations during encoding. We achieve this by decomposing repetitive and manageable
components from video codecs, which can then be handled using Incrementally Verifiable Computation (IVC). By providing a formal definition and security model for proofs of video authenticity, we demonstrate the security of Eva under well-established
cryptographic assumptions.

To make Eva efficient, we construct an IVC based on folding schemes that incorporate lookup arguments, resulting in a linear-time prover whose proofs can be compressed to a constant size. We further improve the performance of Eva through various
optimizations, including tailored circuit design and GPU acceleration. The evaluation of our implementation shows that Eva is practical: for a $1$-minute HD ($1280 \times 720$) video encoded in H.264 at $30$ frames per second, Eva generates a proof in
about $2.5$ hours on consumer-grade hardware at a speed of $5.5$ μs per pixel, surpassing previous cryptographic image authentication schemes that support arbitrary editing operations by more than an order of magnitude.



## 2024/1437

* Title: HierNet: A Hierarchical Deep Learning Model for SCA on Long Traces
* Authors: Suvadeep Hajra, Debdeep Mukhopadhyay
* [Permalink](https://eprint.iacr.org/2024/1437)
* [Download](https://eprint.iacr.org/2024/1437.pdf)

### Abstract

Side-channel analysis (SCA) compromises the security of cryptographic devices by exploiting various side-channel leakages such as power consumption, electromagnetic (EM) emanations, or timing variations, posing a practical threat to the security and
privacy of modern digital systems. In power or EM SCA, statistical or machine learning methods are employed to extract secret information from power/EM traces. In many practical scenarios, raw power/EM traces can span hundreds of thousands of features,
with relevant leakages occurring over only a few small segments. Consequently, existing SCAs often select a small number of features before launching the attack, making their success highly dependent on the feasibility of feature selection. However,
feature selection may not always be possible, such as in the presence of countermeasures like masking or jitters.

Several recent works have employed deep learning (DL) methods to conduct SCA on long raw traces, thereby reducing dependence on feature selection steps. However, these methods often perform poorly against various jitter-based countermeasures. While some
of these methods have shown high robustness to jitter-based countermeasures on relatively shorter traces, we demonstrate in this work that their performance deteriorates as trace lengths increase. Based on these observations, we develop a hierarchical DL
model for SCA on long traces that is robust against various countermeasures. The proposed model, HierNet, extracts information from long traces using a two-level information assimilation process. At the base level, a DL model with shift-invariance is
employed to extract information from smaller trace segments. Subsequently, a top-level DL model integrates the outputs of the base model to generate the final output. The proposed model has been experimentally evaluated against various combinations of
masking, random delay, and clock jitter countermeasures using traces with lengths exceeding $200K$ features. The results have been compared with three existing SCA benchmark models. They demonstrate HierNet's superiority in several scenarios, such as on
long traces, against clock jitter countermeasures, and low training data scenarios. In particular, while other models fail to reach the guessing entropy $1$ using as many as $5K$ traces, HierNet achieves the same with fewer than or close to $10$ traces.

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