Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
[digest] 2023 Week 14
16 views
Skip to first unread message
IACR ePrint Archive
Apr 9, 2023, 3:21:25 PM4/9/23
to
## In this issue
1. [2023/476] A private set intersection protocol based on multi- ...
2. [2023/477] Separations among formulations of non-malleable ...
3. [2023/478] TENET : Sublogarithmic Proof, Sublinear Verifier ...
4. [2023/479] Spherical Gaussian Leftover Hash Lemma via the ...
5. [2023/480] Practical Homomorphic Evaluation of Block-Cipher- ...
6. [2023/481] A Framework for UC Secure Privacy Preserving ...
7. [2023/482] Homomorphic Trapdoors for Identity-based and Group ...
8. [2023/483] Unbounded Predicate Inner Product Functional ...
9. [2023/484] SCA Evaluation and Benchmarking of Finalists in the ...
10. [2023/485] Practically-exploitable Cryptographic ...
11. [2023/486] Flamingo: Multi-Round Single-Server Secure ...
12. [2023/487] On the State of Crypto-Agility
13. [2023/488] The Planted $k$-SUM Problem: Algorithms, Lower ...
14. [2023/489] Shorter and Faster Identity-Based Signatures with ...
15. [2023/490] Quantum Public-Key Encryption with Tamper-Resilient ...
16. [2023/491] On the Security of Blind Signatures in the Multi- ...
17. [2023/492] Batch Signatures, Revisited
18. [2023/493] Force: Making 4PC > 4 × PC in Privacy Preserving ...
19. [2023/494] Spartan and Bulletproofs are simulation-extractable ...
20. [2023/495] On the algebraic immunity of weightwise perfectly ...
21. [2023/496] Evaluating the Security of Block Ciphers Against ...
22. [2023/497] Upper bounding the number of bent functions using ...
23. [2023/498] Subset-optimized BLS Multi-signature with Key ...
24. [2023/499] FLUTE: Fast and Secure Lookup Table Evaluations ...
25. [2023/500] Non-Interactive Quantum Key Distribution
26. [2023/501] New Ways to Garble Arithmetic Circuits
27. [2023/502] Laconic Function Evaluation for Turing Machines
28. [2023/503] Neural Network Quantisation for Faster Homomorphic ...
## 2023/476
* Title: A private set intersection protocol based on multi-party quantum computation for greatest common divisor
* Authors: Muhammad Imran
* [Permalink](https://eprint.iacr.org/2023/476)
* [Download](https://eprint.iacr.org/2023/476.pdf)
### Abstract
Private set intersection (PSI) is a cryptographic primitive that allows two or more parties to learn the intersection of their input sets and nothing else. In this paper, we present a private set intersection protocol based on a new secure multi-party quantum protocol for greatest common divisor (GCD). The protocol is mainly inspired by the recent quantum private set union protocol based on least common multiple by Liu, Yang, and Li. Performance analysis guarantees the correctness and it also shows that the proposed protocols are completely secure in semi-honest model. Moreover, the complexity is proven to be efficient (poly logarithmic) in the size of the input sets.
## 2023/477
* Title: Separations among formulations of non-malleable encryption under valid ciphertext condition
* Authors: Yodai Watanabe
* [Permalink](https://eprint.iacr.org/2023/477)
* [Download](https://eprint.iacr.org/2023/477.pdf)
### Abstract
Non-malleability is one of the basic security goals for encryption schemes which ensures the resistance of the scheme against ciphertext modifications in the sense that any adversary, given a ciphertext of a plaintext, cannot generate another ciphertext whose underlying plaintext is meaningfully related to the initial one. There are multiple formulations of non-malleable encryption schemes, depending on whether they are based on simulation or comparison, or whether they impose valid ciphertext condition, in which an adversary is required to generate only valid ciphertexts, or not. In addition to the simulation-based and comparison-based formulations (SNM and CNM), an indistinguishability-based characterization of non-malleability (IND), called ciphertext indistinguishability against parallel chosen-ciphertext attacks has been proposed. These three formulations, SNM, CNM and IND, have been shown equivalent if the valid ciphertext condition is not imposed; however, if that condition is imposed, then they have been shown equivalent only against the strongest type of attack models, and the relations among them against the weaker types of the attack models remain open. This work answers this open question by showing the separations SNM*$\not\rightarrow$CNM* and IND*$\not\rightarrow$SNM* against the weaker types of the attack models, where the asterisk attached to the short-hand notations represents that the valid ciphertext condition is imposed. Moreover, motivated by the proof of the latter separation, this paper introduces simulation-based and comparison-based formulations of semantic security (SSS* and CSS*) against parallel chosen-ciphertext attacks, and shows the equivalences SSS*$\leftrightarrow$SNM* and CSS*$\leftrightarrow$CNM* against all types of the attack models. It thus follows that IND*$\not\rightarrow$SSS*, that is, semantic security and ciphertext indistinguishability, which have been shown equivalent in various settings, separate against the weaker parallel chosen-ciphertext attacks under the valid ciphertext condition.
## 2023/478
* Title: TENET : Sublogarithmic Proof, Sublinear Verifier Inner Product Argument without a Trusted Setup
* Authors: Hyeonbum Lee, Jae Hong Seo
* [Permalink](https://eprint.iacr.org/2023/478)
* [Download](https://eprint.iacr.org/2023/478.pdf)
### Abstract
We propose a new inner product argument (IPA), called TENET, which features sublogarithmic proof size and sublinear verifier without a trusted setup. IPA is a core primitive for various advanced proof systems including range proofs, circuit satisfiability, and polynomial commitment, particularly where a trusted setup is hard to apply. At ASIACRYPT 2022, Kim, Lee, and Seo showed that pairings can be utilized to exceed the complexity barrier of the previous discrete logarithm-based IPA without a trusted setup. More precisely, they proposed two pairing-based IPAs, one with sublogarithmic proof size and the other one with sublinear verifier cost, but they left achieving both complexities simultaneously as an open problem.
We investigate the obstacles for this open problem and then provide our solution TENET, which achieves both sublogarithmic proof size and sublinear verifier. We prove the soundness of TENET under the discrete logarithm assumption and double pairing assumption.
## 2023/479
* Title: Spherical Gaussian Leftover Hash Lemma via the Rényi Divergence
* Authors: Hiroki Okada, Kazuhide Fukushima, Shinsaku Kiyomoto, Tsuyoshi Takagi
* [Permalink](https://eprint.iacr.org/2023/479)
* [Download](https://eprint.iacr.org/2023/479.pdf)
### Abstract
Agrawal et al. (Asiacrypt 2013) proved the discrete Gaussian leftover hash lemma, which states that the linear transformation of the discrete spherical Gaussian is statistically close to the discrete ellipsoid Gaussian. Showing that it is statistically close to the discrete spherical Gaussian, which we call the discrete spherical Gaussian leftover hash lemma (SGLHL), is an open problem posed by Agrawal et al. In this paper, we solve the problem in a weak sense: we show that the distribution of the linear transformation of the discrete spherical Gaussian and the discrete spherical Gaussian are close with respect to the Rényi divergence (RD), which we call the weak SGLHL (wSGLHL).
As an application of wSGLHL, we construct a sharper self-reduction of the learning with errors problem (LWE) problem. Applebaum et al. (CRYPTO 2009) showed that linear sums of LWE samples are statistically close to (plain) LWE samples with some unknown error parameter. In contrast, we show that linear sums of LWE samples and (plain) LWE samples with a known error parameter are close with respect to RD. As another application, we weaken the independence heuristic required for the fully homomorphic encryption scheme TFHE.
## 2023/480
* Title: Practical Homomorphic Evaluation of Block-Cipher-Based Hash Functions with Applications
* Authors: Adda-Akram Bendoukha, Oana Stan, Renaud Sirdey, Nicolas Quero, Luciano Freitas
* [Permalink](https://eprint.iacr.org/2023/480)
* [Download](https://eprint.iacr.org/2023/480.pdf)
### Abstract
Fully homomorphic encryption (FHE) is a powerful cryptographic technique allowing to perform computation directly over encrypted data. Motivated by the overhead induced by the homomorphic ciphertexts during encryption and transmission, the transciphering technique, consisting in switching from a symmetric encryption to FHE encrypted data was investigated in several papers. Different stream and block ciphers were evaluated in terms of their "FHE-friendliness", meaning practical implementations costs while maintaining sufficient security levels.
In this work, we present a first evaluation of hash functions in the homomorphic domain, based on well-chosen block ciphers. More precisely, we investigate the cost of transforming PRINCE, SIMON, SPECK, and LowMC, a set of lightweight block-ciphers into secure hash primitives using well-established hash functions constructions based on block-ciphers, and provide evaluation under bootstrappable FHE schemes. We also motivate the necessity of practical homomorphic evaluation of hash functions by providing several use cases in which the integrity of private data is also required. In particular, our hash constructions can be of significant use in a threshold-homomorphic based protocol for the single secret leader election problem occurring in blockchains with Proof-of-stake consensus. Our experiments showed that using a TFHE implementation of a hash function, we are able to achieve practical runtime, and appropriate security levels (e.g., for PRINCE it takes 1.28 minutes to obtain a 128 bits of hash).
## 2023/481
* Title: A Framework for UC Secure Privacy Preserving Biometric Authentication using Efficient Functional Encryption
* Authors: Johannes Ernst, Aikaterini Mitrokotsa
* [Permalink](https://eprint.iacr.org/2023/481)
* [Download](https://eprint.iacr.org/2023/481.pdf)
### Abstract
Despite its popularity, password based authentication is susceptible to various kinds of attacks, such as online or offline dictionary attacks. Employing biometric credentials in the authentication process can strengthen the provided security guarantees, but raises significant privacy concerns. This is mainly due to the inherent variability of biometric readings that prevents us from simply applying a standard hash function to them. In this paper we first propose an ideal functionality for modeling secure, privacy preserving biometric based two-factor authentication in the framework of universal composability (UC). The functionality is of independent interest and can be used to analyze other two-factor authentication protocols. We then present a generic protocol for biometric based two-factor authentication and prove its security (relative to our proposed functionality) in the UC framework. The first factor in our protocol is the possession of a device that stores the required secret keys and the second factor is the user's biometric template. Our construction can be instantiated with function hiding functional encryption, which computes for example the distance of the encrypted templates or the predicate indicating whether the templates are close enough. Our contribution can be split into three parts:
- We model privacy preserving biometric based two-factor authentication as an ideal functionality in the UC framework. To the best of our knowledge, this is the first description of an ideal functionality for biometric based two-factor authentication in the UC framework.
- We propose a general protocol that uses functional encryption and prove that it UC-realizes our ideal functionality.
- We show how to instantiate our framework with efficient, state of the art inner-product functional encryption. This allows the computation of the Euclidean distance, Hamming distance or cosine similarity between encrypted biometric templates. In order to show its practicality, we implemented our protocol and evaluated its performance.
## 2023/482
* Title: Homomorphic Trapdoors for Identity-based and Group Signatures
* Authors: Buvana Ganesh, Apurva Vangujar, Alia Umrani, Paolo Palmieri
* [Permalink](https://eprint.iacr.org/2023/482)
* [Download](https://eprint.iacr.org/2023/482.pdf)
### Abstract
Group signature (GS) schemes are an important primitive in cryptography that provides anonymity and traceability for a group of users. In this paper, we propose a new approach to constructing GS schemes using the homomorphic trapdoor function (HTDF). We focus on constructing an identity-based homomorphic signature (IBHS) scheme using the trapdoor, providing a simpler scheme that has no zero-knowledge proofs. Our scheme allows packing more data into the signatures by elevating the existing homomorphic trapdoor from the SIS assumption to the MSIS assumption to enable packing techniques. Compared to the existing group signature schemes, we provide a straightforward and alternate construction that is efficient and secure under the standard model. Overall, our proposed scheme provides an efficient and secure solution for GS schemes using HTDF.
## 2023/483
* Title: Unbounded Predicate Inner Product Functional Encryption from Pairings
* Authors: Uddipana Dowerah, Subhranil Dutta, Aikaterini Mitrokotsa, Sayantan Mukherjee, Tapas Pal
* [Permalink](https://eprint.iacr.org/2023/483)
* [Download](https://eprint.iacr.org/2023/483.pdf)
### Abstract
Predicate inner product functional encryption (P-IPFE) is essentially attribute-based IPFE (AB-IPFE) which additionally hides attributes associated to ciphertexts. In a P-IPFE, a message x is encrypted under an attribute w and a secret key is generated for a pair (y, v) such that recovery of ⟨x, y⟩ requires the vectors w, v to satisfy a linear relation. We call a P-IPFE unbounded if it can encrypt unbounded length attributes and message vectors.
• zero predicate IPFE. We construct the first unbounded zero predicate IPFE (UZP-IPFE) which recovers ⟨x,y⟩ if ⟨w,v⟩ = 0. This construction is inspired by the unbounded IPFE of Tomida and Takashima (ASIACRYPT 2018) and the unbounded zero inner product encryption of Okamoto and Takashima (ASIACRYPT 2012). The UZP-IPFE stands secure against general attackers capable of decrypting the challenge ciphertext. Concretely, it provides full attribute-hiding security in the indistinguishability-based semi-adaptive model under the standard symmetric external Diffie-Hellman assumption.
• non-zero predicate IPFE. We present the first unbounded non-zero predicate IPFE (UNP-IPFE) that successfully recovers ⟨x, y⟩ if ⟨w, v⟩ ≠ 0. We generically transform an unbounded quadratic FE (UQFE) scheme to weak attribute-hiding UNP-IPFE in both public and secret key settings. Interestingly, our secret key simulation secure UNP-IPFE has succinct secret keys and is constructed from a novel succinct UQFE that we build in the random oracle model. We leave the problem of constructing a succinct public key UNP-IPFE or UQFE in the standard model as an important open problem.
## 2023/484
* Title: SCA Evaluation and Benchmarking of Finalists in the NIST Lightweight Cryptography Standardization Process
* Authors: Kamyar Mohajerani, Luke Beckwith, Abubakr Abdulgadir, Eduardo Ferrufino, Jens-Peter Kaps, Kris Gaj
* [Permalink](https://eprint.iacr.org/2023/484)
* [Download](https://eprint.iacr.org/2023/484.pdf)
### Abstract
Side-channel resistance is one of the primary criteria identified by NIST for use in evaluating candidates in the Lightweight Cryptography (LWC) Standardization process. In Rounds 1 and 2 of this process, when the number of candidates was still substantial (56 and 32, respectively), evaluating this feature was close to impossible. With ten finalists remaining, side-channel resistance and its effect on the performance and cost of practical implementations became of utmost importance. In this paper, we describe a general framework for evaluating the side-channel resistance of LWC candidates using resources, experience, and general practices of the cryptographic engineering community developed over the last two decades. The primary features of our approach are a) self-identification and self-characterization of side-channel security evaluation labs, b) distributed development of protected hardware and software implementations, matching certain high-level requirements and deliverable formats, and c) dynamic and transparent matching of evaluators with implementers in order to achieve the most meaningful and fair evaluation report. After the classes of hardware implementations with similar resistance to side-channel attacks are established, these implementations are comprehensively benchmarked using Xilinx Artix-7 FPGAs. All implementations belonging to the same class are then ranked according to several performance and cost metrics. Four candidates - Ascon, Xoodyak, TinyJAMBU, and ISAP - are selected as offering unique advantages over other finalists in terms of the throughput, area, throughput-to-area ratio, or randomness requirements of their protected hardware implementations.
## 2023/485
* Title: Practically-exploitable Cryptographic Vulnerabilities in Matrix
* Authors: Martin R. Albrecht, Sofía Celi, Benjamin Dowling, Daniel Jones
* [Permalink](https://eprint.iacr.org/2023/485)
* [Download](https://eprint.iacr.org/2023/485.pdf)
### Abstract
We report several practically-exploitable cryptographic vulnerabilities in the Matrix standard for federated real-time communication and its flagship client and prototype implementation, Element. These, together, invalidate the confidentiality and authentication guarantees claimed by Matrix against a malicious server. This is despite Matrix’ cryptographic routines being constructed from well-known and -studied cryptographic building blocks. The vulnerabilities we exploit differ in their nature (insecure by design, protocol confusion, lack of domain separation, implementation bugs) and are distributed broadly across the different subprotocols and libraries that make up the cryptographic core of Matrix and Element. Together, these vulnerabilities highlight the need for a systematic and formal analysis of the cryptography in the Matrix standard.
## 2023/486
* Title: Flamingo: Multi-Round Single-Server Secure Aggregation with Applications to Private Federated Learning
* Authors: Yiping Ma, Jess Woods, Sebastian Angel, Antigoni Polychroniadou, Tal Rabin
* [Permalink](https://eprint.iacr.org/2023/486)
* [Download](https://eprint.iacr.org/2023/486.pdf)
### Abstract
This paper introduces Flamingo, a system for secure aggregation of data across a large set of clients. In secure aggregation, a server sums up the private inputs of clients and obtains the result without learning anything about the individual inputs beyond what is implied by the final sum. Flamingo focuses on the multi-round setting found in federated learning in which many consecutive summations (averages) of model weights are performed to derive a good model. Previous protocols, such as Bell et al. (CCS ’20), have been designed for a single round and are adapted to the federated learning setting by repeating the protocol multiple times. Flamingo eliminates the need for the per-round setup of previous protocols, and has a new lightweight dropout resilience protocol to ensure that if clients leave in the middle of a sum the server can still obtain a meaningful result. Furthermore, Flamingo introduces a new way to locally choose the so-called client neighborhood introduced by Bell et al. These techniques help Flamingo reduce the number of interactions between clients and the server, resulting in a significant reduction in the end-to-end runtime for a full training session over prior work.
We implement and evaluate Flamingo and show that it can securely train a neural network on the (Extended) MNIST and CIFAR-100 datasets, and the model converges without a loss in accuracy, compared to a non-private federated learning system.
## 2023/487
* Title: On the State of Crypto-Agility
* Authors: Nouri Alnahawi, Nicolai Schmitt, Alexander Wiesmaier, Andreas Heinemann, Tobias Grasmeyer
* [Permalink](https://eprint.iacr.org/2023/487)
* [Download](https://eprint.iacr.org/2023/487.pdf)
### Abstract
The demand for crypto-agility, although dating back for more than two decades, recently started to increase in the light of the expected post-quantum cryptography (PQC) migration. Nevertheless, it started to evolve into a science on its own. Therefore, it is important to establish a unified definition of the notion, as well as its related aspects, scope, and practical applications. This paper presents a literature survey on crypto-agility and discusses respective development efforts categorized into different areas, including requirements, characteristics, and possible challenges. We explore the need for crypto-agility beyond PQC algorithms and security protocols and shed some light on current solutions, existing automation mechanisms, and best practices in this field. We evaluate the state of readiness for crypto-agility, and offer a discussion on the identified open issues. The results of our survey indicate a need for a comprehensive understanding. Further, more agile design paradigms are required in developing new IT systems, and in refactoring existing ones, in order to realize crypto-agility on a broad scale.
## 2023/488
* Title: The Planted $k$-SUM Problem: Algorithms, Lower Bounds, Hardness Amplification, and Cryptography
* Authors: Sagnik Saha, Nikolaj Ignatieff Schwartzbach, Prashant Nalini Vasudevan
* [Permalink](https://eprint.iacr.org/2023/488)
* [Download](https://eprint.iacr.org/2023/488.pdf)
### Abstract
In the average-case $k$-SUM problem, given $r$ integers chosen uniformly at random from $\{0,\ldots,M-1\}$, the objective is to find a set of $k$ numbers that sum to 0 modulo $M$ (this set is called a "solution"). In the related $k$-XOR problem, given $k$ uniformly random Boolean vectors of length log $M$, the objective is to find a set of $k$ of them whose bitwise-XOR is the all-zero vector. Both of these problems have widespread applications in the study of fine-grained complexity and cryptanalysis.
The feasibility and complexity of these problems depends on the relative values of $k$, $r$, and $M$. The dense regime of $M \leq r^k$, where solutions exist with high probability, is quite well-understood and we have several non-trivial algorithms and hardness conjectures here. Much less is known about the sparse regime of $M\gg r^k$, where solutions are unlikely to exist. The best answers we have for many fundamental questions here are limited to whatever carries over from the dense or worst-case settings.
We study the planted $k$-SUM and $k$-XOR problems in the sparse regime. In these problems, a random solution is planted in a randomly generated instance and has to be recovered. As $M$ increases past $r^k$, these planted solutions tend to be the only solutions with increasing probability, potentially becoming easier to find. We show several results about the complexity and applications of these problems.
Conditional Lower Bounds. Assuming established conjectures about the hardness of average-case (non-planted) $k$-SUM when $M = r^k$, we show non-trivial lower bounds on the running time of algorithms for planted $k$-SUM when $r^k\leq M\leq r^{2k}$. We show the same for $k$-XOR as well.
Search-to-Decision Reduction. For any $M>r^k$, suppose there is an algorithm running in time $T$ that can distinguish between a random $k$-SUM instance and a random instance with a planted solution, with success probability $(1-o(1))$. Then, for the same $M$, there is an algorithm running in time $\tilde{O}(T)$ that solves planted $k$-SUM with constant probability. The same holds for $k$-XOR as well.
Hardness Amplification. For any $M \geq r^k$, if an algorithm running in time $T$ solves planted $k$-XOR with success probability $\Omega(1/\text{polylog}(r))$, then there is an algorithm running in time $\tilde O(T)$ that solves it with probability $(1-o(1))$. We show this by constructing a rapidly mixing random walk over $k$-XOR instances that preserves the planted solution.
Cryptography. For some $M \leq 2^{\text{polylog}(r)}$, the hardness of the $k$-XOR problem can be used to construct Public-Key Encryption (PKE) assuming that the Learning Parity with Noise (LPN) problem with constant noise rate is hard for $2^{n^{0.01}}$-time algorithms. Previous constructions of PKE from LPN needed either a noise rate of $O(1/\sqrt{n})$, or hardness for $2^{n^{0.5}}$-time algorithms.
Algorithms. For any $M \geq 2^{r^2}$, there is a constant $c$ (independent of $k$) and an algorithm running in time $r^c$ that, for any $k$, solves planted $k$-SUM with success probability $\Omega(1/8^k)$. We get this by showing an average-case reduction from planted $k$-SUM to the Subset Sum problem. For $r^k \leq M \ll 2^{r^2}$, the best known algorithms are still the worst-case $k$-SUM algorithms running in time $r^{\lceil{k/2}\rceil-o(1)}$.
## 2023/489
* Title: Shorter and Faster Identity-Based Signatures with Tight Security in the (Q)ROM from Lattices
* Authors: Eric Sageloli, Pierre Pébereau, Pierrick Méaux, Céline Chevalier
* [Permalink](https://eprint.iacr.org/2023/489)
* [Download](https://eprint.iacr.org/2023/489.pdf)
### Abstract
We provide identity-based signature (IBS) schemes with tight security against adaptive adversaries, in the (classical or quantum) random oracle model (ROM or QROM), in both unstructured and structured lattices, based on the SIS or RSIS assumption. These signatures are short (of size independent of the message length).
Our schemes build upon a work from Pan and Wagner (PQCrypto’21) and improve on it in several ways. First, we prove their transformation from non-adaptive to adaptive IBS in the QROM. Then, we simplify the parameters used and give concrete values. Finally, we simplify the signature scheme by using a non-homogeneous relation, which helps us reduce the size of the signature and get rid of one costly trapdoor delegation.
On the whole, we get better security bounds, shorter signatures and faster algorithms.
## 2023/490
* Title: Quantum Public-Key Encryption with Tamper-Resilient Public Keys from One-Way Functions
* Authors: Fuyuki Kitagawa, Tomoyuki Morimae, Ryo Nishimaki, Takashi Yamakawa
* [Permalink](https://eprint.iacr.org/2023/490)
* [Download](https://eprint.iacr.org/2023/490.pdf)
### Abstract
We construct quantum public-key encryption from one-way functions. In our construction, public keys are quantum, but ciphertexts are classical. Quantum public-key encryption from one-way functions (or weaker primitives such as pseudorandom function-like states) are also proposed in some recent works [Morimae-Yamakawa, eprint:2022/1336; Coladangelo, eprint:2023/282; Grilo-Sattath-Vu, eprint:2023/345; Barooti-Malavolta-Walter, eprint:2023/306]. However, they have a huge drawback: they are secure only when quantum public keys can be transmitted to the sender (who runs the encryption algorithm) without being tampered with by the adversary, which seems to require unsatisfactory physical setup assumptions such as secure quantum channels. Our construction is free from such a drawback: it guarantees the secrecy of the encrypted messages even if we assume only unauthenticated quantum channels. Thus, the encryption is done with adversarially tampered quantum public keys. Our construction based only on one-way functions is the first quantum public-key encryption that achieves the goal of classical public-key encryption, namely, to establish secure communication over insecure channels.
## 2023/491
* Title: On the Security of Blind Signatures in the Multi-Signer Setting
* Authors: Samuel Bedassa Alemu, Julia Kastner
* [Permalink](https://eprint.iacr.org/2023/491)
* [Download](https://eprint.iacr.org/2023/491.pdf)
### Abstract
Blind signatures were originally introduced by Chaum (CRYPTO ’82) in the context of privacy-preserving electronic payment systems. Nowadays, the cryptographic primitive has also found applications in anonymous credentials and voting systems. However, many practical blind signature schemes have only been analysed in the game-based setting where a single signer is present. This is somewhat unsatisfactory as blind signatures are intended to be deployed in a setting with many signers. We address this in the following ways:
– We formalise two variants of one-more-unforgeability of blind signatures in the Multi-Signer Setting.
– We show that one-more-unforgeability in the Single-Signer Setting translates straightforwardly to the Multi-Signer Setting with a reduction loss proportional to the number of signers.
– We identify a class of blind signature schemes which we call Key-Convertible where this reduction loss can be traded for an increased number of signing sessions in the Single-Signer Setting and show that many practical blind signature schemes such as blind BLS, blind Schnorr, blind Okamoto-Schnorr as well as two pairing-free, ROS immune schemes by Tessaro and Zhu (Eurocrypt’22) fulfil this property.
– We further describe how the notion of key substitution attacks (Menezes and Smart, DCC’04) can be translated to blind signatures and provide a generic transformation of how they can be avoided.
## 2023/492
* Title: Batch Signatures, Revisited
* Authors: Carlos Aguilar-Melchor, Martin R. Albrecht, Thomas Bailleux, Nina Bindel, James Howe, Andreas Hülsing, David Joseph, Marc Manzano
* [Permalink](https://eprint.iacr.org/2023/492)
* [Download](https://eprint.iacr.org/2023/492.pdf)
### Abstract
We revisit batch signatures (previously considered in a draft RFC, and used in multiple recent works), where a single, potentially expensive, "inner" digital signature authenticates a Merkle tree constructed from many messages. We formalise a construction and prove its unforgeability and privacy properties.
We also show that batch signing allows us to scale slow signing algorithms, such as those recently selected for standardisation as part of NIST's post-quantum project, to high throughput, with a mild increase in latency. For the example of Falcon-512 in TLS, we can increase the amount of connections per second by a factor 3.2x, at the cost of an increase in the signature size by ~14% and the median latency by ~25%, where both are ran on the same 30 core server.
We also discuss applications where batch signatures allow us to increase throughput and to save bandwidth. For example, again for Falcon-512, once one batch signature is available, the additional bandwidth for each of the remaining N-1 is only 82 bytes.
## 2023/493
* Title: Force: Making 4PC > 4 × PC in Privacy Preserving Machine Learning on GPU
* Authors: Tianxiang Dai, Li Duan, Yufan Jiang, Yong Li, Fei Mei, Yulian Sun
* [Permalink](https://eprint.iacr.org/2023/493)
* [Download](https://eprint.iacr.org/2023/493.pdf)
### Abstract
Tremendous efforts have been made to improve the
efficiency of secure Multi-Party Computation (MPC), which
allows n ≥ 2 parties to jointly evaluate a target function
without leaking their own private inputs. It has been confirmed
by previous researchers that 3-Party Computation (3PC) and
outsourcing computations to GPUs can lead to huge performance improvement of MPC in computationally intensive
tasks such as Privacy-Preserving Machine Learning (PPML).
A natural question to ask is whether super-linear performance
gain is possible for a linear increase in resources. In this paper,
we give an affirmative answer to this question.
We propose Force, an extremely efficient 4PC system for
PPML. To the best of our knowledge, each party in Force
enjoys the least number of local computations and lowest data
exchanges between parties. This is achieved by introducing
a new sharing type X -share along with MPC protocols in
privacy-preserving training and inference that are semi-honest
secure with an honest-majority. Our contribution does not stop
at theory. We also propose engineering optimizations and verify
the high performance of the protocols with implementation and
experiments. By comparing the results with state-of-the-art
researches such as Cheetah, Piranha, CryptGPU and CrypTen,
we showcase that Force is sound and extremely efficient, as it
can improve the PPML performance by a factor of 2 to 1200
compared with other latest 2PC, 3PC and 4PC system
## 2023/494
* Title: Spartan and Bulletproofs are simulation-extractable (for free!)
* Authors: Quang Dao, Paul Grubbs
* [Permalink](https://eprint.iacr.org/2023/494)
* [Download](https://eprint.iacr.org/2023/494.pdf)
### Abstract
Increasing deployment of advanced zero-knowledge proof systems, especially zkSNARKs, has raised critical questions about their security against real-world attacks. Two classes of attacks of concern in practice are adaptive soundness attacks, where an attacker can prove false statements by choosing its public input after generating a proof, and malleability attacks, where an attacker can use a valid proof to create another valid proof it could not have created itself. Prior work has shown that simulation-extractability (SIM-EXT), a strong notion of security for proof systems, rules out these attacks.
In this paper, we prove that two transparent, discrete-log-based zkSNARKs, Spartan and Bulletproofs, are simulation-extractable (SIM-EXT) in the random oracle model if the discrete logarithm assumption holds in the underlying group. Since these assumptions are required to prove standard security properties for Spartan and Bulletproofs, our results show that SIM-EXT is, surprisingly, "for free" with these schemes. Our result is the first SIM-EXT proof for Spartan and encompasses both linear- and sublinear-verifier variants. Our result for Bulletproofs encompasses both the aggregate range proof and arithmetic circuit variants, and is the first to not rely on the algebraic group model (AGM), resolving an open question posed by Ganesh et al. (EUROCRYPT '22). As part of our analysis, we develop a generalization of the tree-builder extraction theorem of Attema et al. (TCC '22), which may be of independent interest.
## 2023/495
* Title: On the algebraic immunity of weightwise perfectly balanced functions
* Authors: Agnese Gini, Pierrick Méaux
* [Permalink](https://eprint.iacr.org/2023/495)
* [Download](https://eprint.iacr.org/2023/495.pdf)
### Abstract
In this article we study the Algebraic Immunity (AI) of Weightwise Perfectly Balanced (WPB) functions.
After showing a lower bound on the AI of two classes of WPB functions from the previous literature, we prove that the minimal AI of a WPB $n$-variables function is constant, equal to $2$ for $n\ge 4$ .
Then, we compute the distribution of the AI of WPB function in $4$ variables, and estimate the one in $8$ and $16$ variables.
For these values of $n$ we observe that a large majority of WPB functions have optimal AI, and that we could not obtain an AI-$2$ WPB function by sampling at random.
Finally, we address the problem of constructing WPB functions with bounded algebraic immunity, exploiting a construction from 2022 by Gini and Méaux. In particular, we present a method to generate multiple WPB functions with minimal AI, and we prove that the WPB functions with high nonlinearity exhibited by Gini and Méaux also have minimal AI. We conclude with a construction giving WPB functions with lower bounded AI, and give as example a family with all elements with AI at least $n/2-\log(n)+1$.
## 2023/496
* Title: Evaluating the Security of Block Ciphers Against Zero-correlation Linear Attack in the Distinguishers Aspect
* Authors: Xichao Hu, Yongqiang Li, Lin Jiao, Zhengbin Liu, Mingsheng Wang
* [Permalink](https://eprint.iacr.org/2023/496)
* [Download](https://eprint.iacr.org/2023/496.pdf)
### Abstract
Zero-correlation linear attack is a powerful attack of block ciphers, the lower number of rounds (LNR) which no its distinguisher (named zero-correlation linear approximation, ZCLA) exists reflects the ability of a block cipher against the zero-correlation linear attack. However, due to the large search space, showing there are no ZCLAs exist for a given block cipher under a certain number of rounds is a very hard task. Thus, present works can only prove there no ZCLAs exist in a small search space, such as 1-bit/nibble/word input and output active ZCLAs, which still exist very large gaps to show no ZCLAs exist in the whole search space.
In this paper, we propose the meet-in-the-middle method and double-collision method to show there no ZCLAs exist in the whole search space. The basic ideas of those two methods are very simple, but they work very effectively. As a result, we apply those two methods to AES, Midori64, and ARIA, and show that there no ZCLAs exist for $5$-round AES without the last Mix-Column layer, $7$-round Midori64 without the last Mix-Column layer, and $5$-round ARIA without the last linear layer.
As far as we know, our method is the first automatic method that can be used to show there no ZCLAs exist in the whole search space, which can provide sufficient evidence to show the security of a block cipher against the zero-correlation linear attack in the distinguishers aspect, this feature is very useful for designing block ciphers.
## 2023/497
* Title: Upper bounding the number of bent functions using 2-row bent rectangles
* Authors: Sergey Agievich
* [Permalink](https://eprint.iacr.org/2023/497)
* [Download](https://eprint.iacr.org/2023/497.pdf)
### Abstract
Using the representation of bent functions by bent rectangles, that is, special matrices with restrictions on columns and rows, we obtain an upper bound on the number of bent functions that improves previously known bounds in a practical range of dimensions.
The core of our method is the following fact based on the recent observation by Potapov (arXiv:2107.14583): a 2-row bent rectangle is completely defined by one of its rows and the remaining values in slightly more than half of the columns.
## 2023/498
* Title: Subset-optimized BLS Multi-signature with Key Aggregation
* Authors: Foteini Baldimtsi, Konstantinos Kryptos Chalkias, Francois Garillot, Jonas Lindstrom, Ben Riva, Arnab Roy, Alberto Sonnino, Pun Waiwitlikhit, Joy Wang
* [Permalink](https://eprint.iacr.org/2023/498)
* [Download](https://eprint.iacr.org/2023/498.pdf)
### Abstract
We propose a variant of the original Boneh, Drijvers, and Neven (Asiacrypt '18) BLS multi-signature aggregation scheme best suited to applications where the full set of potential signers is fixed and known and any subset $I$ of this group can create a multi-signature over a message $m$. This setup is very common in proof-of-stake blockchains where a $2f+1$ majority of $3f$ validators sign transactions and/or blocks and is secure against $\textit{rogue-key}$ attacks without requiring a proof of key possession mechanism.
In our scheme, instead of randomizing the aggregated signatures, we have a one-time randomization phase of the public keys: each public key is replaced by a sticky randomized version (for which each participant can still compute the derived private key). The main benefit compared to the original Boneh at al. approach is that since our randomization process happens only once and not per signature we can have significant savings during aggregation and verification. Specifically, for a subset $I$ of $t$ signers, we save $t$ exponentiations in $\mathbb{G}_2$ at aggregation and $t$ exponentiations in $\mathbb{G}_1$ at verification or vice versa, depending on which BLS mode we prefer: $\textit{minPK}$ (public keys in $\mathbb{G}_1$) or $\textit{minSig}$ (signatures in $\mathbb{G}_1$).
Interestingly, our security proof requires a significant departure from the co-CDH based proof of Boneh at al. When $n$ (size of the universal set of signers) is small, we prove our protocol secure in the Algebraic Group and Random Oracle models based on the Discrete Log problem. For larger $n$, our proof also requires the Random Modular Subset Sum (RMSS) problem.
## 2023/499
* Title: FLUTE: Fast and Secure Lookup Table Evaluations (Full Version)
* Authors: Andreas Brüggemann, Robin Hundt, Thomas Schneider, Ajith Suresh, Hossein Yalame
* [Permalink](https://eprint.iacr.org/2023/499)
* [Download](https://eprint.iacr.org/2023/499.pdf)
### Abstract
The concept of using Lookup Tables (LUTs) instead of Boolean circuits is well-known and been widely applied in a variety of applications, including FPGAs, image processing, and database management systems. In cryptography, using such LUTs instead of conventional gates like AND and XOR results in more compact circuits and has been shown to substantially improve online performance when evaluated with secure multi-party computation. Several recent works on secure floating-point computations and privacy-preserving machine learning inference rely heavily on existing LUT techniques. However, they suffer from either large overhead in the setup phase or subpar online performance.
We propose FLUTE, a novel protocol for secure LUT evaluation with good setup and online performance. In a two-party setting, we show that FLUTE matches or even outperforms the online performance of all prior approaches, while being competitive in terms of overall performance with the best prior LUT protocols. In addition, we provide an open-source implementation of FLUTE written in the Rust programming language, and implementations of the Boolean secure two-party computation protocols of ABY2.0 and silent OT. We find that FLUTE outperforms the state of the art by two orders of magnitude in the online phase while retaining similar overall communication.
## 2023/500
* Title: Non-Interactive Quantum Key Distribution
* Authors: Giulio Malavolta, Michael Walter
* [Permalink](https://eprint.iacr.org/2023/500)
* [Download](https://eprint.iacr.org/2023/500.pdf)
### Abstract
Quantum key distribution (QKD) allows Alice and Bob to agree on a shared secret key, while communicating over a public (untrusted) quantum channel.
Compared to classical key exchange, it has two main advantages:
(i)The key is unconditionally hidden to the eyes of any attacker, and
(ii) its security assumes only the existence of authenticated classical channels which, in practice, can be realized using Minicrypt assumptions, such as the existence of digital signatures.
On the flip side, QKD protocols typically require multiple rounds of interactions, whereas classical key exchange can be realized with the minimal amount of two messages. A long-standing open question is whether QKD requires more rounds of interaction than classical key exchange.
In this work, we propose a two-message QKD protocol that satisfies everlasting security, assuming only the existence of quantum-secure one-way functions.
That is, the shared key is unconditionally hidden, provided computational assumptions hold during the protocol execution. Our result follows from a new quantum cryptographic primitive that we introduce in this work: the quantum-public-key one-time pad, a public-key analogue of the well-known one-time pad.
## 2023/501
* Title: New Ways to Garble Arithmetic Circuits
* Authors: Marshall Ball, Hanjun Li, Huijia Lin, Tianren Liu
* [Permalink](https://eprint.iacr.org/2023/501)
* [Download](https://eprint.iacr.org/2023/501.pdf)
### Abstract
The beautiful work of Applebaum, Ishai, and Kushilevitz [FOCS'11] initiated the study of arithmetic variants of Yao's garbled circuits. An arithmetic garbling scheme is an efficient transformation that converts an arithmetic circuit $C: \mathcal{R}^n \rightarrow \mathcal{R}^m$ over a ring $\mathcal{R}$ into a garbled circuit $\widehat C$ and $n$ affine functions $L_i$ for $i \in [n]$, such that $\widehat C$ and $L_i(x_i)$ reveals only the output $C(x)$ and no other information of $x$. AIK presented the first arithmetic garbling scheme supporting computation over integers from a bounded (possibly exponentially large) range, based on Learning With Errors (LWE). In contrast, converting $C$ into a Boolean circuit and applying Yao's garbled circuit treats the inputs as bit strings instead of ring elements, and hence is not "arithmetic".
In this work, we present new ways to garble arithmetic circuits, which improve the state-of-the-art on efficiency, modularity, and functionality. To measure efficiency, we define the rate of a garbling scheme as the maximal ratio between the bit-length of the garbled circuit $|\widehat C|$ and that of the computation tableau $|C|\ell$ in the clear, where $\ell$ is the bit length of wire values (e.g., Yao's garbled circuit has rate $O(\lambda)$).
$\bullet$ We present the first constant-rate arithmetic garbled circuit for computation over large integers based on the Decisional Composite Residuosity (DCR) assumption, significantly improving the efficiency of the schemes of Applebaum, Ishai, and Kushilevitz.
$\bullet$ We construct an arithmetic garbling scheme for modular computation over $\mathcal{R} = \mathbb{Z}_p$ for any integer modulus $p$, based on either DCR or LWE. The DCR-based instantiation achieves rate $O(\lambda)$ for large $p$. Furthermore, our construction is modular and makes black-box use of the underlying ring and a simple key extension gadget.
$\bullet$ We describe a variant of the first scheme supporting arithmetic circuits over bounded integers that are augmented with Boolean computation (e.g., truncation of an integer value, and comparison between two values), while keeping the constant rate when garbling the arithmetic part.
To the best of our knowledge, constant-rate (Boolean or arithmetic) garbling was only achieved before using the powerful primitive of indistinguishability obfuscation, or for restricted circuits with small depth.
## 2023/502
* Title: Laconic Function Evaluation for Turing Machines
* Authors: Nico Döttling, Phillip Gajland, Giulio Malavolta
* [Permalink](https://eprint.iacr.org/2023/502)
* [Download](https://eprint.iacr.org/2023/502.pdf)
### Abstract
Laconic function evaluation (LFE) allows Alice to compress a large circuit $\mathbf{C}$ into a small digest $\mathsf{d}$. Given Alice's digest, Bob can encrypt some input $x$ under $\mathsf{d}$ in a way that enables Alice to recover $\mathbf{C}(x)$, without learning anything beyond that. The scheme is said to be $laconic$ if the size of $\mathsf{d}$, the runtime of the encryption algorithm, and the size of the ciphertext are all sublinear in the size of $\mathbf{C}$.
Until now, all known LFE constructions have ciphertexts whose size depends on the $depth$ of the circuit $\mathbf{C}$, akin to the limitation of $levelled$ homomorphic encryption. In this work we close this gap and present the first LFE scheme (for Turing machines) with asymptotically optimal parameters. Our scheme assumes the existence of indistinguishability obfuscation and somewhere statistically binding hash functions.
As further contributions, we show how our scheme enables a wide range of new applications, including two previously unknown constructions:
• Non-interactive zero-knowledge (NIZK) proofs with optimal prover complexity.
• Witness encryption and attribute-based encryption (ABE) for Turing machines from falsifiable assumptions.
## 2023/503
* Title: Neural Network Quantisation for Faster Homomorphic Encryption
* Authors: Wouter Legiest, Jan-Pieter D'Anvers, Michiel Van Beirendonck, Furkan Turan, Ingrid Verbauwhede
* [Permalink](https://eprint.iacr.org/2023/503)
* [Download](https://eprint.iacr.org/2023/503.pdf)
### Abstract
Homomorphic encryption (HE) enables calculating
on encrypted data, which makes it possible to perform privacy-
preserving neural network inference. One disadvantage of this
technique is that it is several orders of magnitudes slower than
calculation on unencrypted data. Neural networks are commonly
trained using floating-point, while most homomorphic encryption
libraries calculate on integers, thus requiring a quantisation of the
neural network. A straightforward approach would be to quantise
to large integer sizes (e.g., 32 bit) to avoid large quantisation errors.
In this work, we reduce the integer sizes of the networks, using
quantisation-aware training, to allow more efficient computations.
For the targeted MNIST architecture proposed by Badawi et al., we reduce the integer sizes by 33% without significant loss
of accuracy, while for the CIFAR architecture, we can reduce the
integer sizes by 43%. Implementing the resulting networks under
the BFV homomorphic encryption scheme using SEAL, we could
reduce the execution time of an MNIST neural network by 80%
and by 40% for a CIFAR neural network.
1. [2023/476] A private set intersection protocol based on multi- ...
2. [2023/477] Separations among formulations of non-malleable ...
3. [2023/478] TENET : Sublogarithmic Proof, Sublinear Verifier ...
4. [2023/479] Spherical Gaussian Leftover Hash Lemma via the ...
5. [2023/480] Practical Homomorphic Evaluation of Block-Cipher- ...
6. [2023/481] A Framework for UC Secure Privacy Preserving ...
7. [2023/482] Homomorphic Trapdoors for Identity-based and Group ...
8. [2023/483] Unbounded Predicate Inner Product Functional ...
9. [2023/484] SCA Evaluation and Benchmarking of Finalists in the ...
10. [2023/485] Practically-exploitable Cryptographic ...
11. [2023/486] Flamingo: Multi-Round Single-Server Secure ...
12. [2023/487] On the State of Crypto-Agility
13. [2023/488] The Planted $k$-SUM Problem: Algorithms, Lower ...
14. [2023/489] Shorter and Faster Identity-Based Signatures with ...
15. [2023/490] Quantum Public-Key Encryption with Tamper-Resilient ...
16. [2023/491] On the Security of Blind Signatures in the Multi- ...
17. [2023/492] Batch Signatures, Revisited
18. [2023/493] Force: Making 4PC > 4 × PC in Privacy Preserving ...
19. [2023/494] Spartan and Bulletproofs are simulation-extractable ...
20. [2023/495] On the algebraic immunity of weightwise perfectly ...
21. [2023/496] Evaluating the Security of Block Ciphers Against ...
22. [2023/497] Upper bounding the number of bent functions using ...
23. [2023/498] Subset-optimized BLS Multi-signature with Key ...
24. [2023/499] FLUTE: Fast and Secure Lookup Table Evaluations ...
25. [2023/500] Non-Interactive Quantum Key Distribution
26. [2023/501] New Ways to Garble Arithmetic Circuits
27. [2023/502] Laconic Function Evaluation for Turing Machines
28. [2023/503] Neural Network Quantisation for Faster Homomorphic ...
## 2023/476
* Title: A private set intersection protocol based on multi-party quantum computation for greatest common divisor
* Authors: Muhammad Imran
* [Permalink](https://eprint.iacr.org/2023/476)
* [Download](https://eprint.iacr.org/2023/476.pdf)
### Abstract
Private set intersection (PSI) is a cryptographic primitive that allows two or more parties to learn the intersection of their input sets and nothing else. In this paper, we present a private set intersection protocol based on a new secure multi-party quantum protocol for greatest common divisor (GCD). The protocol is mainly inspired by the recent quantum private set union protocol based on least common multiple by Liu, Yang, and Li. Performance analysis guarantees the correctness and it also shows that the proposed protocols are completely secure in semi-honest model. Moreover, the complexity is proven to be efficient (poly logarithmic) in the size of the input sets.
## 2023/477
* Title: Separations among formulations of non-malleable encryption under valid ciphertext condition
* Authors: Yodai Watanabe
* [Permalink](https://eprint.iacr.org/2023/477)
* [Download](https://eprint.iacr.org/2023/477.pdf)
### Abstract
Non-malleability is one of the basic security goals for encryption schemes which ensures the resistance of the scheme against ciphertext modifications in the sense that any adversary, given a ciphertext of a plaintext, cannot generate another ciphertext whose underlying plaintext is meaningfully related to the initial one. There are multiple formulations of non-malleable encryption schemes, depending on whether they are based on simulation or comparison, or whether they impose valid ciphertext condition, in which an adversary is required to generate only valid ciphertexts, or not. In addition to the simulation-based and comparison-based formulations (SNM and CNM), an indistinguishability-based characterization of non-malleability (IND), called ciphertext indistinguishability against parallel chosen-ciphertext attacks has been proposed. These three formulations, SNM, CNM and IND, have been shown equivalent if the valid ciphertext condition is not imposed; however, if that condition is imposed, then they have been shown equivalent only against the strongest type of attack models, and the relations among them against the weaker types of the attack models remain open. This work answers this open question by showing the separations SNM*$\not\rightarrow$CNM* and IND*$\not\rightarrow$SNM* against the weaker types of the attack models, where the asterisk attached to the short-hand notations represents that the valid ciphertext condition is imposed. Moreover, motivated by the proof of the latter separation, this paper introduces simulation-based and comparison-based formulations of semantic security (SSS* and CSS*) against parallel chosen-ciphertext attacks, and shows the equivalences SSS*$\leftrightarrow$SNM* and CSS*$\leftrightarrow$CNM* against all types of the attack models. It thus follows that IND*$\not\rightarrow$SSS*, that is, semantic security and ciphertext indistinguishability, which have been shown equivalent in various settings, separate against the weaker parallel chosen-ciphertext attacks under the valid ciphertext condition.
## 2023/478
* Title: TENET : Sublogarithmic Proof, Sublinear Verifier Inner Product Argument without a Trusted Setup
* Authors: Hyeonbum Lee, Jae Hong Seo
* [Permalink](https://eprint.iacr.org/2023/478)
* [Download](https://eprint.iacr.org/2023/478.pdf)
### Abstract
We propose a new inner product argument (IPA), called TENET, which features sublogarithmic proof size and sublinear verifier without a trusted setup. IPA is a core primitive for various advanced proof systems including range proofs, circuit satisfiability, and polynomial commitment, particularly where a trusted setup is hard to apply. At ASIACRYPT 2022, Kim, Lee, and Seo showed that pairings can be utilized to exceed the complexity barrier of the previous discrete logarithm-based IPA without a trusted setup. More precisely, they proposed two pairing-based IPAs, one with sublogarithmic proof size and the other one with sublinear verifier cost, but they left achieving both complexities simultaneously as an open problem.
We investigate the obstacles for this open problem and then provide our solution TENET, which achieves both sublogarithmic proof size and sublinear verifier. We prove the soundness of TENET under the discrete logarithm assumption and double pairing assumption.
## 2023/479
* Title: Spherical Gaussian Leftover Hash Lemma via the Rényi Divergence
* Authors: Hiroki Okada, Kazuhide Fukushima, Shinsaku Kiyomoto, Tsuyoshi Takagi
* [Permalink](https://eprint.iacr.org/2023/479)
* [Download](https://eprint.iacr.org/2023/479.pdf)
### Abstract
Agrawal et al. (Asiacrypt 2013) proved the discrete Gaussian leftover hash lemma, which states that the linear transformation of the discrete spherical Gaussian is statistically close to the discrete ellipsoid Gaussian. Showing that it is statistically close to the discrete spherical Gaussian, which we call the discrete spherical Gaussian leftover hash lemma (SGLHL), is an open problem posed by Agrawal et al. In this paper, we solve the problem in a weak sense: we show that the distribution of the linear transformation of the discrete spherical Gaussian and the discrete spherical Gaussian are close with respect to the Rényi divergence (RD), which we call the weak SGLHL (wSGLHL).
As an application of wSGLHL, we construct a sharper self-reduction of the learning with errors problem (LWE) problem. Applebaum et al. (CRYPTO 2009) showed that linear sums of LWE samples are statistically close to (plain) LWE samples with some unknown error parameter. In contrast, we show that linear sums of LWE samples and (plain) LWE samples with a known error parameter are close with respect to RD. As another application, we weaken the independence heuristic required for the fully homomorphic encryption scheme TFHE.
## 2023/480
* Title: Practical Homomorphic Evaluation of Block-Cipher-Based Hash Functions with Applications
* Authors: Adda-Akram Bendoukha, Oana Stan, Renaud Sirdey, Nicolas Quero, Luciano Freitas
* [Permalink](https://eprint.iacr.org/2023/480)
* [Download](https://eprint.iacr.org/2023/480.pdf)
### Abstract
Fully homomorphic encryption (FHE) is a powerful cryptographic technique allowing to perform computation directly over encrypted data. Motivated by the overhead induced by the homomorphic ciphertexts during encryption and transmission, the transciphering technique, consisting in switching from a symmetric encryption to FHE encrypted data was investigated in several papers. Different stream and block ciphers were evaluated in terms of their "FHE-friendliness", meaning practical implementations costs while maintaining sufficient security levels.
In this work, we present a first evaluation of hash functions in the homomorphic domain, based on well-chosen block ciphers. More precisely, we investigate the cost of transforming PRINCE, SIMON, SPECK, and LowMC, a set of lightweight block-ciphers into secure hash primitives using well-established hash functions constructions based on block-ciphers, and provide evaluation under bootstrappable FHE schemes. We also motivate the necessity of practical homomorphic evaluation of hash functions by providing several use cases in which the integrity of private data is also required. In particular, our hash constructions can be of significant use in a threshold-homomorphic based protocol for the single secret leader election problem occurring in blockchains with Proof-of-stake consensus. Our experiments showed that using a TFHE implementation of a hash function, we are able to achieve practical runtime, and appropriate security levels (e.g., for PRINCE it takes 1.28 minutes to obtain a 128 bits of hash).
## 2023/481
* Title: A Framework for UC Secure Privacy Preserving Biometric Authentication using Efficient Functional Encryption
* Authors: Johannes Ernst, Aikaterini Mitrokotsa
* [Permalink](https://eprint.iacr.org/2023/481)
* [Download](https://eprint.iacr.org/2023/481.pdf)
### Abstract
Despite its popularity, password based authentication is susceptible to various kinds of attacks, such as online or offline dictionary attacks. Employing biometric credentials in the authentication process can strengthen the provided security guarantees, but raises significant privacy concerns. This is mainly due to the inherent variability of biometric readings that prevents us from simply applying a standard hash function to them. In this paper we first propose an ideal functionality for modeling secure, privacy preserving biometric based two-factor authentication in the framework of universal composability (UC). The functionality is of independent interest and can be used to analyze other two-factor authentication protocols. We then present a generic protocol for biometric based two-factor authentication and prove its security (relative to our proposed functionality) in the UC framework. The first factor in our protocol is the possession of a device that stores the required secret keys and the second factor is the user's biometric template. Our construction can be instantiated with function hiding functional encryption, which computes for example the distance of the encrypted templates or the predicate indicating whether the templates are close enough. Our contribution can be split into three parts:
- We model privacy preserving biometric based two-factor authentication as an ideal functionality in the UC framework. To the best of our knowledge, this is the first description of an ideal functionality for biometric based two-factor authentication in the UC framework.
- We propose a general protocol that uses functional encryption and prove that it UC-realizes our ideal functionality.
- We show how to instantiate our framework with efficient, state of the art inner-product functional encryption. This allows the computation of the Euclidean distance, Hamming distance or cosine similarity between encrypted biometric templates. In order to show its practicality, we implemented our protocol and evaluated its performance.
## 2023/482
* Title: Homomorphic Trapdoors for Identity-based and Group Signatures
* Authors: Buvana Ganesh, Apurva Vangujar, Alia Umrani, Paolo Palmieri
* [Permalink](https://eprint.iacr.org/2023/482)
* [Download](https://eprint.iacr.org/2023/482.pdf)
### Abstract
Group signature (GS) schemes are an important primitive in cryptography that provides anonymity and traceability for a group of users. In this paper, we propose a new approach to constructing GS schemes using the homomorphic trapdoor function (HTDF). We focus on constructing an identity-based homomorphic signature (IBHS) scheme using the trapdoor, providing a simpler scheme that has no zero-knowledge proofs. Our scheme allows packing more data into the signatures by elevating the existing homomorphic trapdoor from the SIS assumption to the MSIS assumption to enable packing techniques. Compared to the existing group signature schemes, we provide a straightforward and alternate construction that is efficient and secure under the standard model. Overall, our proposed scheme provides an efficient and secure solution for GS schemes using HTDF.
## 2023/483
* Title: Unbounded Predicate Inner Product Functional Encryption from Pairings
* Authors: Uddipana Dowerah, Subhranil Dutta, Aikaterini Mitrokotsa, Sayantan Mukherjee, Tapas Pal
* [Permalink](https://eprint.iacr.org/2023/483)
* [Download](https://eprint.iacr.org/2023/483.pdf)
### Abstract
Predicate inner product functional encryption (P-IPFE) is essentially attribute-based IPFE (AB-IPFE) which additionally hides attributes associated to ciphertexts. In a P-IPFE, a message x is encrypted under an attribute w and a secret key is generated for a pair (y, v) such that recovery of ⟨x, y⟩ requires the vectors w, v to satisfy a linear relation. We call a P-IPFE unbounded if it can encrypt unbounded length attributes and message vectors.
• zero predicate IPFE. We construct the first unbounded zero predicate IPFE (UZP-IPFE) which recovers ⟨x,y⟩ if ⟨w,v⟩ = 0. This construction is inspired by the unbounded IPFE of Tomida and Takashima (ASIACRYPT 2018) and the unbounded zero inner product encryption of Okamoto and Takashima (ASIACRYPT 2012). The UZP-IPFE stands secure against general attackers capable of decrypting the challenge ciphertext. Concretely, it provides full attribute-hiding security in the indistinguishability-based semi-adaptive model under the standard symmetric external Diffie-Hellman assumption.
• non-zero predicate IPFE. We present the first unbounded non-zero predicate IPFE (UNP-IPFE) that successfully recovers ⟨x, y⟩ if ⟨w, v⟩ ≠ 0. We generically transform an unbounded quadratic FE (UQFE) scheme to weak attribute-hiding UNP-IPFE in both public and secret key settings. Interestingly, our secret key simulation secure UNP-IPFE has succinct secret keys and is constructed from a novel succinct UQFE that we build in the random oracle model. We leave the problem of constructing a succinct public key UNP-IPFE or UQFE in the standard model as an important open problem.
## 2023/484
* Title: SCA Evaluation and Benchmarking of Finalists in the NIST Lightweight Cryptography Standardization Process
* Authors: Kamyar Mohajerani, Luke Beckwith, Abubakr Abdulgadir, Eduardo Ferrufino, Jens-Peter Kaps, Kris Gaj
* [Permalink](https://eprint.iacr.org/2023/484)
* [Download](https://eprint.iacr.org/2023/484.pdf)
### Abstract
Side-channel resistance is one of the primary criteria identified by NIST for use in evaluating candidates in the Lightweight Cryptography (LWC) Standardization process. In Rounds 1 and 2 of this process, when the number of candidates was still substantial (56 and 32, respectively), evaluating this feature was close to impossible. With ten finalists remaining, side-channel resistance and its effect on the performance and cost of practical implementations became of utmost importance. In this paper, we describe a general framework for evaluating the side-channel resistance of LWC candidates using resources, experience, and general practices of the cryptographic engineering community developed over the last two decades. The primary features of our approach are a) self-identification and self-characterization of side-channel security evaluation labs, b) distributed development of protected hardware and software implementations, matching certain high-level requirements and deliverable formats, and c) dynamic and transparent matching of evaluators with implementers in order to achieve the most meaningful and fair evaluation report. After the classes of hardware implementations with similar resistance to side-channel attacks are established, these implementations are comprehensively benchmarked using Xilinx Artix-7 FPGAs. All implementations belonging to the same class are then ranked according to several performance and cost metrics. Four candidates - Ascon, Xoodyak, TinyJAMBU, and ISAP - are selected as offering unique advantages over other finalists in terms of the throughput, area, throughput-to-area ratio, or randomness requirements of their protected hardware implementations.
## 2023/485
* Title: Practically-exploitable Cryptographic Vulnerabilities in Matrix
* Authors: Martin R. Albrecht, Sofía Celi, Benjamin Dowling, Daniel Jones
* [Permalink](https://eprint.iacr.org/2023/485)
* [Download](https://eprint.iacr.org/2023/485.pdf)
### Abstract
We report several practically-exploitable cryptographic vulnerabilities in the Matrix standard for federated real-time communication and its flagship client and prototype implementation, Element. These, together, invalidate the confidentiality and authentication guarantees claimed by Matrix against a malicious server. This is despite Matrix’ cryptographic routines being constructed from well-known and -studied cryptographic building blocks. The vulnerabilities we exploit differ in their nature (insecure by design, protocol confusion, lack of domain separation, implementation bugs) and are distributed broadly across the different subprotocols and libraries that make up the cryptographic core of Matrix and Element. Together, these vulnerabilities highlight the need for a systematic and formal analysis of the cryptography in the Matrix standard.
## 2023/486
* Title: Flamingo: Multi-Round Single-Server Secure Aggregation with Applications to Private Federated Learning
* Authors: Yiping Ma, Jess Woods, Sebastian Angel, Antigoni Polychroniadou, Tal Rabin
* [Permalink](https://eprint.iacr.org/2023/486)
* [Download](https://eprint.iacr.org/2023/486.pdf)
### Abstract
This paper introduces Flamingo, a system for secure aggregation of data across a large set of clients. In secure aggregation, a server sums up the private inputs of clients and obtains the result without learning anything about the individual inputs beyond what is implied by the final sum. Flamingo focuses on the multi-round setting found in federated learning in which many consecutive summations (averages) of model weights are performed to derive a good model. Previous protocols, such as Bell et al. (CCS ’20), have been designed for a single round and are adapted to the federated learning setting by repeating the protocol multiple times. Flamingo eliminates the need for the per-round setup of previous protocols, and has a new lightweight dropout resilience protocol to ensure that if clients leave in the middle of a sum the server can still obtain a meaningful result. Furthermore, Flamingo introduces a new way to locally choose the so-called client neighborhood introduced by Bell et al. These techniques help Flamingo reduce the number of interactions between clients and the server, resulting in a significant reduction in the end-to-end runtime for a full training session over prior work.
We implement and evaluate Flamingo and show that it can securely train a neural network on the (Extended) MNIST and CIFAR-100 datasets, and the model converges without a loss in accuracy, compared to a non-private federated learning system.
## 2023/487
* Title: On the State of Crypto-Agility
* Authors: Nouri Alnahawi, Nicolai Schmitt, Alexander Wiesmaier, Andreas Heinemann, Tobias Grasmeyer
* [Permalink](https://eprint.iacr.org/2023/487)
* [Download](https://eprint.iacr.org/2023/487.pdf)
### Abstract
The demand for crypto-agility, although dating back for more than two decades, recently started to increase in the light of the expected post-quantum cryptography (PQC) migration. Nevertheless, it started to evolve into a science on its own. Therefore, it is important to establish a unified definition of the notion, as well as its related aspects, scope, and practical applications. This paper presents a literature survey on crypto-agility and discusses respective development efforts categorized into different areas, including requirements, characteristics, and possible challenges. We explore the need for crypto-agility beyond PQC algorithms and security protocols and shed some light on current solutions, existing automation mechanisms, and best practices in this field. We evaluate the state of readiness for crypto-agility, and offer a discussion on the identified open issues. The results of our survey indicate a need for a comprehensive understanding. Further, more agile design paradigms are required in developing new IT systems, and in refactoring existing ones, in order to realize crypto-agility on a broad scale.
## 2023/488
* Title: The Planted $k$-SUM Problem: Algorithms, Lower Bounds, Hardness Amplification, and Cryptography
* Authors: Sagnik Saha, Nikolaj Ignatieff Schwartzbach, Prashant Nalini Vasudevan
* [Permalink](https://eprint.iacr.org/2023/488)
* [Download](https://eprint.iacr.org/2023/488.pdf)
### Abstract
In the average-case $k$-SUM problem, given $r$ integers chosen uniformly at random from $\{0,\ldots,M-1\}$, the objective is to find a set of $k$ numbers that sum to 0 modulo $M$ (this set is called a "solution"). In the related $k$-XOR problem, given $k$ uniformly random Boolean vectors of length log $M$, the objective is to find a set of $k$ of them whose bitwise-XOR is the all-zero vector. Both of these problems have widespread applications in the study of fine-grained complexity and cryptanalysis.
The feasibility and complexity of these problems depends on the relative values of $k$, $r$, and $M$. The dense regime of $M \leq r^k$, where solutions exist with high probability, is quite well-understood and we have several non-trivial algorithms and hardness conjectures here. Much less is known about the sparse regime of $M\gg r^k$, where solutions are unlikely to exist. The best answers we have for many fundamental questions here are limited to whatever carries over from the dense or worst-case settings.
We study the planted $k$-SUM and $k$-XOR problems in the sparse regime. In these problems, a random solution is planted in a randomly generated instance and has to be recovered. As $M$ increases past $r^k$, these planted solutions tend to be the only solutions with increasing probability, potentially becoming easier to find. We show several results about the complexity and applications of these problems.
Conditional Lower Bounds. Assuming established conjectures about the hardness of average-case (non-planted) $k$-SUM when $M = r^k$, we show non-trivial lower bounds on the running time of algorithms for planted $k$-SUM when $r^k\leq M\leq r^{2k}$. We show the same for $k$-XOR as well.
Search-to-Decision Reduction. For any $M>r^k$, suppose there is an algorithm running in time $T$ that can distinguish between a random $k$-SUM instance and a random instance with a planted solution, with success probability $(1-o(1))$. Then, for the same $M$, there is an algorithm running in time $\tilde{O}(T)$ that solves planted $k$-SUM with constant probability. The same holds for $k$-XOR as well.
Hardness Amplification. For any $M \geq r^k$, if an algorithm running in time $T$ solves planted $k$-XOR with success probability $\Omega(1/\text{polylog}(r))$, then there is an algorithm running in time $\tilde O(T)$ that solves it with probability $(1-o(1))$. We show this by constructing a rapidly mixing random walk over $k$-XOR instances that preserves the planted solution.
Cryptography. For some $M \leq 2^{\text{polylog}(r)}$, the hardness of the $k$-XOR problem can be used to construct Public-Key Encryption (PKE) assuming that the Learning Parity with Noise (LPN) problem with constant noise rate is hard for $2^{n^{0.01}}$-time algorithms. Previous constructions of PKE from LPN needed either a noise rate of $O(1/\sqrt{n})$, or hardness for $2^{n^{0.5}}$-time algorithms.
Algorithms. For any $M \geq 2^{r^2}$, there is a constant $c$ (independent of $k$) and an algorithm running in time $r^c$ that, for any $k$, solves planted $k$-SUM with success probability $\Omega(1/8^k)$. We get this by showing an average-case reduction from planted $k$-SUM to the Subset Sum problem. For $r^k \leq M \ll 2^{r^2}$, the best known algorithms are still the worst-case $k$-SUM algorithms running in time $r^{\lceil{k/2}\rceil-o(1)}$.
## 2023/489
* Title: Shorter and Faster Identity-Based Signatures with Tight Security in the (Q)ROM from Lattices
* Authors: Eric Sageloli, Pierre Pébereau, Pierrick Méaux, Céline Chevalier
* [Permalink](https://eprint.iacr.org/2023/489)
* [Download](https://eprint.iacr.org/2023/489.pdf)
### Abstract
We provide identity-based signature (IBS) schemes with tight security against adaptive adversaries, in the (classical or quantum) random oracle model (ROM or QROM), in both unstructured and structured lattices, based on the SIS or RSIS assumption. These signatures are short (of size independent of the message length).
Our schemes build upon a work from Pan and Wagner (PQCrypto’21) and improve on it in several ways. First, we prove their transformation from non-adaptive to adaptive IBS in the QROM. Then, we simplify the parameters used and give concrete values. Finally, we simplify the signature scheme by using a non-homogeneous relation, which helps us reduce the size of the signature and get rid of one costly trapdoor delegation.
On the whole, we get better security bounds, shorter signatures and faster algorithms.
## 2023/490
* Title: Quantum Public-Key Encryption with Tamper-Resilient Public Keys from One-Way Functions
* Authors: Fuyuki Kitagawa, Tomoyuki Morimae, Ryo Nishimaki, Takashi Yamakawa
* [Permalink](https://eprint.iacr.org/2023/490)
* [Download](https://eprint.iacr.org/2023/490.pdf)
### Abstract
We construct quantum public-key encryption from one-way functions. In our construction, public keys are quantum, but ciphertexts are classical. Quantum public-key encryption from one-way functions (or weaker primitives such as pseudorandom function-like states) are also proposed in some recent works [Morimae-Yamakawa, eprint:2022/1336; Coladangelo, eprint:2023/282; Grilo-Sattath-Vu, eprint:2023/345; Barooti-Malavolta-Walter, eprint:2023/306]. However, they have a huge drawback: they are secure only when quantum public keys can be transmitted to the sender (who runs the encryption algorithm) without being tampered with by the adversary, which seems to require unsatisfactory physical setup assumptions such as secure quantum channels. Our construction is free from such a drawback: it guarantees the secrecy of the encrypted messages even if we assume only unauthenticated quantum channels. Thus, the encryption is done with adversarially tampered quantum public keys. Our construction based only on one-way functions is the first quantum public-key encryption that achieves the goal of classical public-key encryption, namely, to establish secure communication over insecure channels.
## 2023/491
* Title: On the Security of Blind Signatures in the Multi-Signer Setting
* Authors: Samuel Bedassa Alemu, Julia Kastner
* [Permalink](https://eprint.iacr.org/2023/491)
* [Download](https://eprint.iacr.org/2023/491.pdf)
### Abstract
Blind signatures were originally introduced by Chaum (CRYPTO ’82) in the context of privacy-preserving electronic payment systems. Nowadays, the cryptographic primitive has also found applications in anonymous credentials and voting systems. However, many practical blind signature schemes have only been analysed in the game-based setting where a single signer is present. This is somewhat unsatisfactory as blind signatures are intended to be deployed in a setting with many signers. We address this in the following ways:
– We formalise two variants of one-more-unforgeability of blind signatures in the Multi-Signer Setting.
– We show that one-more-unforgeability in the Single-Signer Setting translates straightforwardly to the Multi-Signer Setting with a reduction loss proportional to the number of signers.
– We identify a class of blind signature schemes which we call Key-Convertible where this reduction loss can be traded for an increased number of signing sessions in the Single-Signer Setting and show that many practical blind signature schemes such as blind BLS, blind Schnorr, blind Okamoto-Schnorr as well as two pairing-free, ROS immune schemes by Tessaro and Zhu (Eurocrypt’22) fulfil this property.
– We further describe how the notion of key substitution attacks (Menezes and Smart, DCC’04) can be translated to blind signatures and provide a generic transformation of how they can be avoided.
## 2023/492
* Title: Batch Signatures, Revisited
* Authors: Carlos Aguilar-Melchor, Martin R. Albrecht, Thomas Bailleux, Nina Bindel, James Howe, Andreas Hülsing, David Joseph, Marc Manzano
* [Permalink](https://eprint.iacr.org/2023/492)
* [Download](https://eprint.iacr.org/2023/492.pdf)
### Abstract
We revisit batch signatures (previously considered in a draft RFC, and used in multiple recent works), where a single, potentially expensive, "inner" digital signature authenticates a Merkle tree constructed from many messages. We formalise a construction and prove its unforgeability and privacy properties.
We also show that batch signing allows us to scale slow signing algorithms, such as those recently selected for standardisation as part of NIST's post-quantum project, to high throughput, with a mild increase in latency. For the example of Falcon-512 in TLS, we can increase the amount of connections per second by a factor 3.2x, at the cost of an increase in the signature size by ~14% and the median latency by ~25%, where both are ran on the same 30 core server.
We also discuss applications where batch signatures allow us to increase throughput and to save bandwidth. For example, again for Falcon-512, once one batch signature is available, the additional bandwidth for each of the remaining N-1 is only 82 bytes.
## 2023/493
* Title: Force: Making 4PC > 4 × PC in Privacy Preserving Machine Learning on GPU
* Authors: Tianxiang Dai, Li Duan, Yufan Jiang, Yong Li, Fei Mei, Yulian Sun
* [Permalink](https://eprint.iacr.org/2023/493)
* [Download](https://eprint.iacr.org/2023/493.pdf)
### Abstract
Tremendous efforts have been made to improve the
efficiency of secure Multi-Party Computation (MPC), which
allows n ≥ 2 parties to jointly evaluate a target function
without leaking their own private inputs. It has been confirmed
by previous researchers that 3-Party Computation (3PC) and
outsourcing computations to GPUs can lead to huge performance improvement of MPC in computationally intensive
tasks such as Privacy-Preserving Machine Learning (PPML).
A natural question to ask is whether super-linear performance
gain is possible for a linear increase in resources. In this paper,
we give an affirmative answer to this question.
We propose Force, an extremely efficient 4PC system for
PPML. To the best of our knowledge, each party in Force
enjoys the least number of local computations and lowest data
exchanges between parties. This is achieved by introducing
a new sharing type X -share along with MPC protocols in
privacy-preserving training and inference that are semi-honest
secure with an honest-majority. Our contribution does not stop
at theory. We also propose engineering optimizations and verify
the high performance of the protocols with implementation and
experiments. By comparing the results with state-of-the-art
researches such as Cheetah, Piranha, CryptGPU and CrypTen,
we showcase that Force is sound and extremely efficient, as it
can improve the PPML performance by a factor of 2 to 1200
compared with other latest 2PC, 3PC and 4PC system
## 2023/494
* Title: Spartan and Bulletproofs are simulation-extractable (for free!)
* Authors: Quang Dao, Paul Grubbs
* [Permalink](https://eprint.iacr.org/2023/494)
* [Download](https://eprint.iacr.org/2023/494.pdf)
### Abstract
Increasing deployment of advanced zero-knowledge proof systems, especially zkSNARKs, has raised critical questions about their security against real-world attacks. Two classes of attacks of concern in practice are adaptive soundness attacks, where an attacker can prove false statements by choosing its public input after generating a proof, and malleability attacks, where an attacker can use a valid proof to create another valid proof it could not have created itself. Prior work has shown that simulation-extractability (SIM-EXT), a strong notion of security for proof systems, rules out these attacks.
In this paper, we prove that two transparent, discrete-log-based zkSNARKs, Spartan and Bulletproofs, are simulation-extractable (SIM-EXT) in the random oracle model if the discrete logarithm assumption holds in the underlying group. Since these assumptions are required to prove standard security properties for Spartan and Bulletproofs, our results show that SIM-EXT is, surprisingly, "for free" with these schemes. Our result is the first SIM-EXT proof for Spartan and encompasses both linear- and sublinear-verifier variants. Our result for Bulletproofs encompasses both the aggregate range proof and arithmetic circuit variants, and is the first to not rely on the algebraic group model (AGM), resolving an open question posed by Ganesh et al. (EUROCRYPT '22). As part of our analysis, we develop a generalization of the tree-builder extraction theorem of Attema et al. (TCC '22), which may be of independent interest.
## 2023/495
* Title: On the algebraic immunity of weightwise perfectly balanced functions
* Authors: Agnese Gini, Pierrick Méaux
* [Permalink](https://eprint.iacr.org/2023/495)
* [Download](https://eprint.iacr.org/2023/495.pdf)
### Abstract
In this article we study the Algebraic Immunity (AI) of Weightwise Perfectly Balanced (WPB) functions.
After showing a lower bound on the AI of two classes of WPB functions from the previous literature, we prove that the minimal AI of a WPB $n$-variables function is constant, equal to $2$ for $n\ge 4$ .
Then, we compute the distribution of the AI of WPB function in $4$ variables, and estimate the one in $8$ and $16$ variables.
For these values of $n$ we observe that a large majority of WPB functions have optimal AI, and that we could not obtain an AI-$2$ WPB function by sampling at random.
Finally, we address the problem of constructing WPB functions with bounded algebraic immunity, exploiting a construction from 2022 by Gini and Méaux. In particular, we present a method to generate multiple WPB functions with minimal AI, and we prove that the WPB functions with high nonlinearity exhibited by Gini and Méaux also have minimal AI. We conclude with a construction giving WPB functions with lower bounded AI, and give as example a family with all elements with AI at least $n/2-\log(n)+1$.
## 2023/496
* Title: Evaluating the Security of Block Ciphers Against Zero-correlation Linear Attack in the Distinguishers Aspect
* Authors: Xichao Hu, Yongqiang Li, Lin Jiao, Zhengbin Liu, Mingsheng Wang
* [Permalink](https://eprint.iacr.org/2023/496)
* [Download](https://eprint.iacr.org/2023/496.pdf)
### Abstract
Zero-correlation linear attack is a powerful attack of block ciphers, the lower number of rounds (LNR) which no its distinguisher (named zero-correlation linear approximation, ZCLA) exists reflects the ability of a block cipher against the zero-correlation linear attack. However, due to the large search space, showing there are no ZCLAs exist for a given block cipher under a certain number of rounds is a very hard task. Thus, present works can only prove there no ZCLAs exist in a small search space, such as 1-bit/nibble/word input and output active ZCLAs, which still exist very large gaps to show no ZCLAs exist in the whole search space.
In this paper, we propose the meet-in-the-middle method and double-collision method to show there no ZCLAs exist in the whole search space. The basic ideas of those two methods are very simple, but they work very effectively. As a result, we apply those two methods to AES, Midori64, and ARIA, and show that there no ZCLAs exist for $5$-round AES without the last Mix-Column layer, $7$-round Midori64 without the last Mix-Column layer, and $5$-round ARIA without the last linear layer.
As far as we know, our method is the first automatic method that can be used to show there no ZCLAs exist in the whole search space, which can provide sufficient evidence to show the security of a block cipher against the zero-correlation linear attack in the distinguishers aspect, this feature is very useful for designing block ciphers.
## 2023/497
* Title: Upper bounding the number of bent functions using 2-row bent rectangles
* Authors: Sergey Agievich
* [Permalink](https://eprint.iacr.org/2023/497)
* [Download](https://eprint.iacr.org/2023/497.pdf)
### Abstract
Using the representation of bent functions by bent rectangles, that is, special matrices with restrictions on columns and rows, we obtain an upper bound on the number of bent functions that improves previously known bounds in a practical range of dimensions.
The core of our method is the following fact based on the recent observation by Potapov (arXiv:2107.14583): a 2-row bent rectangle is completely defined by one of its rows and the remaining values in slightly more than half of the columns.
## 2023/498
* Title: Subset-optimized BLS Multi-signature with Key Aggregation
* Authors: Foteini Baldimtsi, Konstantinos Kryptos Chalkias, Francois Garillot, Jonas Lindstrom, Ben Riva, Arnab Roy, Alberto Sonnino, Pun Waiwitlikhit, Joy Wang
* [Permalink](https://eprint.iacr.org/2023/498)
* [Download](https://eprint.iacr.org/2023/498.pdf)
### Abstract
We propose a variant of the original Boneh, Drijvers, and Neven (Asiacrypt '18) BLS multi-signature aggregation scheme best suited to applications where the full set of potential signers is fixed and known and any subset $I$ of this group can create a multi-signature over a message $m$. This setup is very common in proof-of-stake blockchains where a $2f+1$ majority of $3f$ validators sign transactions and/or blocks and is secure against $\textit{rogue-key}$ attacks without requiring a proof of key possession mechanism.
In our scheme, instead of randomizing the aggregated signatures, we have a one-time randomization phase of the public keys: each public key is replaced by a sticky randomized version (for which each participant can still compute the derived private key). The main benefit compared to the original Boneh at al. approach is that since our randomization process happens only once and not per signature we can have significant savings during aggregation and verification. Specifically, for a subset $I$ of $t$ signers, we save $t$ exponentiations in $\mathbb{G}_2$ at aggregation and $t$ exponentiations in $\mathbb{G}_1$ at verification or vice versa, depending on which BLS mode we prefer: $\textit{minPK}$ (public keys in $\mathbb{G}_1$) or $\textit{minSig}$ (signatures in $\mathbb{G}_1$).
Interestingly, our security proof requires a significant departure from the co-CDH based proof of Boneh at al. When $n$ (size of the universal set of signers) is small, we prove our protocol secure in the Algebraic Group and Random Oracle models based on the Discrete Log problem. For larger $n$, our proof also requires the Random Modular Subset Sum (RMSS) problem.
## 2023/499
* Title: FLUTE: Fast and Secure Lookup Table Evaluations (Full Version)
* Authors: Andreas Brüggemann, Robin Hundt, Thomas Schneider, Ajith Suresh, Hossein Yalame
* [Permalink](https://eprint.iacr.org/2023/499)
* [Download](https://eprint.iacr.org/2023/499.pdf)
### Abstract
The concept of using Lookup Tables (LUTs) instead of Boolean circuits is well-known and been widely applied in a variety of applications, including FPGAs, image processing, and database management systems. In cryptography, using such LUTs instead of conventional gates like AND and XOR results in more compact circuits and has been shown to substantially improve online performance when evaluated with secure multi-party computation. Several recent works on secure floating-point computations and privacy-preserving machine learning inference rely heavily on existing LUT techniques. However, they suffer from either large overhead in the setup phase or subpar online performance.
We propose FLUTE, a novel protocol for secure LUT evaluation with good setup and online performance. In a two-party setting, we show that FLUTE matches or even outperforms the online performance of all prior approaches, while being competitive in terms of overall performance with the best prior LUT protocols. In addition, we provide an open-source implementation of FLUTE written in the Rust programming language, and implementations of the Boolean secure two-party computation protocols of ABY2.0 and silent OT. We find that FLUTE outperforms the state of the art by two orders of magnitude in the online phase while retaining similar overall communication.
## 2023/500
* Title: Non-Interactive Quantum Key Distribution
* Authors: Giulio Malavolta, Michael Walter
* [Permalink](https://eprint.iacr.org/2023/500)
* [Download](https://eprint.iacr.org/2023/500.pdf)
### Abstract
Quantum key distribution (QKD) allows Alice and Bob to agree on a shared secret key, while communicating over a public (untrusted) quantum channel.
Compared to classical key exchange, it has two main advantages:
(i)The key is unconditionally hidden to the eyes of any attacker, and
(ii) its security assumes only the existence of authenticated classical channels which, in practice, can be realized using Minicrypt assumptions, such as the existence of digital signatures.
On the flip side, QKD protocols typically require multiple rounds of interactions, whereas classical key exchange can be realized with the minimal amount of two messages. A long-standing open question is whether QKD requires more rounds of interaction than classical key exchange.
In this work, we propose a two-message QKD protocol that satisfies everlasting security, assuming only the existence of quantum-secure one-way functions.
That is, the shared key is unconditionally hidden, provided computational assumptions hold during the protocol execution. Our result follows from a new quantum cryptographic primitive that we introduce in this work: the quantum-public-key one-time pad, a public-key analogue of the well-known one-time pad.
## 2023/501
* Title: New Ways to Garble Arithmetic Circuits
* Authors: Marshall Ball, Hanjun Li, Huijia Lin, Tianren Liu
* [Permalink](https://eprint.iacr.org/2023/501)
* [Download](https://eprint.iacr.org/2023/501.pdf)
### Abstract
The beautiful work of Applebaum, Ishai, and Kushilevitz [FOCS'11] initiated the study of arithmetic variants of Yao's garbled circuits. An arithmetic garbling scheme is an efficient transformation that converts an arithmetic circuit $C: \mathcal{R}^n \rightarrow \mathcal{R}^m$ over a ring $\mathcal{R}$ into a garbled circuit $\widehat C$ and $n$ affine functions $L_i$ for $i \in [n]$, such that $\widehat C$ and $L_i(x_i)$ reveals only the output $C(x)$ and no other information of $x$. AIK presented the first arithmetic garbling scheme supporting computation over integers from a bounded (possibly exponentially large) range, based on Learning With Errors (LWE). In contrast, converting $C$ into a Boolean circuit and applying Yao's garbled circuit treats the inputs as bit strings instead of ring elements, and hence is not "arithmetic".
In this work, we present new ways to garble arithmetic circuits, which improve the state-of-the-art on efficiency, modularity, and functionality. To measure efficiency, we define the rate of a garbling scheme as the maximal ratio between the bit-length of the garbled circuit $|\widehat C|$ and that of the computation tableau $|C|\ell$ in the clear, where $\ell$ is the bit length of wire values (e.g., Yao's garbled circuit has rate $O(\lambda)$).
$\bullet$ We present the first constant-rate arithmetic garbled circuit for computation over large integers based on the Decisional Composite Residuosity (DCR) assumption, significantly improving the efficiency of the schemes of Applebaum, Ishai, and Kushilevitz.
$\bullet$ We construct an arithmetic garbling scheme for modular computation over $\mathcal{R} = \mathbb{Z}_p$ for any integer modulus $p$, based on either DCR or LWE. The DCR-based instantiation achieves rate $O(\lambda)$ for large $p$. Furthermore, our construction is modular and makes black-box use of the underlying ring and a simple key extension gadget.
$\bullet$ We describe a variant of the first scheme supporting arithmetic circuits over bounded integers that are augmented with Boolean computation (e.g., truncation of an integer value, and comparison between two values), while keeping the constant rate when garbling the arithmetic part.
To the best of our knowledge, constant-rate (Boolean or arithmetic) garbling was only achieved before using the powerful primitive of indistinguishability obfuscation, or for restricted circuits with small depth.
## 2023/502
* Title: Laconic Function Evaluation for Turing Machines
* Authors: Nico Döttling, Phillip Gajland, Giulio Malavolta
* [Permalink](https://eprint.iacr.org/2023/502)
* [Download](https://eprint.iacr.org/2023/502.pdf)
### Abstract
Laconic function evaluation (LFE) allows Alice to compress a large circuit $\mathbf{C}$ into a small digest $\mathsf{d}$. Given Alice's digest, Bob can encrypt some input $x$ under $\mathsf{d}$ in a way that enables Alice to recover $\mathbf{C}(x)$, without learning anything beyond that. The scheme is said to be $laconic$ if the size of $\mathsf{d}$, the runtime of the encryption algorithm, and the size of the ciphertext are all sublinear in the size of $\mathbf{C}$.
Until now, all known LFE constructions have ciphertexts whose size depends on the $depth$ of the circuit $\mathbf{C}$, akin to the limitation of $levelled$ homomorphic encryption. In this work we close this gap and present the first LFE scheme (for Turing machines) with asymptotically optimal parameters. Our scheme assumes the existence of indistinguishability obfuscation and somewhere statistically binding hash functions.
As further contributions, we show how our scheme enables a wide range of new applications, including two previously unknown constructions:
• Non-interactive zero-knowledge (NIZK) proofs with optimal prover complexity.
• Witness encryption and attribute-based encryption (ABE) for Turing machines from falsifiable assumptions.
## 2023/503
* Title: Neural Network Quantisation for Faster Homomorphic Encryption
* Authors: Wouter Legiest, Jan-Pieter D'Anvers, Michiel Van Beirendonck, Furkan Turan, Ingrid Verbauwhede
* [Permalink](https://eprint.iacr.org/2023/503)
* [Download](https://eprint.iacr.org/2023/503.pdf)
### Abstract
Homomorphic encryption (HE) enables calculating
on encrypted data, which makes it possible to perform privacy-
preserving neural network inference. One disadvantage of this
technique is that it is several orders of magnitudes slower than
calculation on unencrypted data. Neural networks are commonly
trained using floating-point, while most homomorphic encryption
libraries calculate on integers, thus requiring a quantisation of the
neural network. A straightforward approach would be to quantise
to large integer sizes (e.g., 32 bit) to avoid large quantisation errors.
In this work, we reduce the integer sizes of the networks, using
quantisation-aware training, to allow more efficient computations.
For the targeted MNIST architecture proposed by Badawi et al., we reduce the integer sizes by 33% without significant loss
of accuracy, while for the CIFAR architecture, we can reduce the
integer sizes by 43%. Implementing the resulting networks under
the BFV homomorphic encryption scheme using SEAL, we could
reduce the execution time of an MNIST neural network by 80%
and by 40% for a CIFAR neural network.
0 new messages