Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
[digest] 2023 Week 22
18 views
Skip to first unread message
IACR ePrint Archive
Jun 4, 2023, 3:19:47 PM6/4/23
to
## In this issue
1. [2022/1332] On the Classic Protocol for MPC Schnorr Signatures
2. [2022/1507] Label Correlation in Deep Learning-based Side- ...
3. [2023/207] On Quantum Secure Compressing Pseudorandom Functions
4. [2023/549] Weak instances of class group action based ...
5. [2023/757] A Note on ``On the Design of Mutual Authentication ...
6. [2023/758] Scaling Mobile Private Contact Discovery to ...
7. [2023/759] Efficient TFHE Bootstrapping in the Multiparty Setting
8. [2023/760] Time to Bribe: Measuring Block Construction Market
9. [2023/761] Nimble: Rollback Protection for Confidential Cloud ...
10. [2023/762] How to Design Fair Protocols in the Multi- ...
11. [2023/763] Undetectable Watermarks for Language Models
12. [2023/764] Subversion-Resilient Authenticated Encryption ...
13. [2023/765] Threshold ECDSA in Three Rounds
14. [2023/766] Lattice-based Commit-Transferrable Signatures and ...
15. [2023/767] LFHE: Fully Homomorphic Encryption with ...
16. [2023/768] Owl: An Augmented Password-Authenticated Key ...
17. [2023/769] Brakedown's expander code
18. [2023/770] Towards compressed permutation oracles
19. [2023/771] Revisiting Key Decomposition Techniques for FHE: ...
20. [2023/772] Classical and Quantum Meet-in-the-Middle ...
21. [2023/773] An update on Keccak performance on ARMv7-M
22. [2023/774] Tagged Chameleon Hash from Lattice and Application ...
23. [2023/775] Exact Security Analysis of ASCON
24. [2023/776] Quantum Attacks on Type-1 Generalized Feistel Schemes
25. [2023/777] Too Many Hints - When LLL Breaks LWE
26. [2023/778] Bounded Verification for Finite-Field-Blasting (In ...
27. [2023/779] Hidden Stabilizers, the Isogeny To Endomorphism ...
28. [2023/780] An Anonymous Multi-receiver Certificateless Hybrid ...
29. [2023/781] $\mathsf{Skye}$: A Fast KDF based on Expanding PRF ...
30. [2023/782] Coefficient Grouping for Complex Affine Layers
31. [2023/783] Breaking the power-of-two barrier: noise estimation ...
32. [2023/784] History-Free Sequential Aggregate Signatures from ...
33. [2023/785] Generation of two ''independent'' points on an ...
34. [2023/786] Blockchain Transaction Censorship: (In)secure and ...
35. [2023/787] Private Proof-of-Stake Blockchains using ...
36. [2023/788] A flexible Snark via the monomial basis
## 2022/1332
* Title: On the Classic Protocol for MPC Schnorr Signatures
* Authors: Nikolaos Makriyannis
* [Permalink](https://eprint.iacr.org/2022/1332)
* [Download](https://eprint.iacr.org/2022/1332.pdf)
### Abstract
In this paper, we prove that the classic three-round protocol for MPC Schnorr Signatures is fully-adaptive UC-secure. Furthermore, we show that a simple variant of the Classic protocol achieves tight security, i.e.~the security of the resulting, modified, protocol tightly reduces to the security of the underlying non-MPC scheme.
## 2022/1507
* Title: Label Correlation in Deep Learning-based Side-channel Analysis
* Authors: Lichao Wu, Léo Weissbart, Marina Krček, Huimin Li, Guilherme Perin, Lejla Batina, Stjepan Picek
* [Permalink](https://eprint.iacr.org/2022/1507)
* [Download](https://eprint.iacr.org/2022/1507.pdf)
### Abstract
The efficiency of the profiling side-channel analysis can be significantly improved with machine learning techniques. Although powerful, a fundamental machine learning limitation of being data-hungry received little attention in the side-channel community. In practice, the maximum number of leakage traces that evaluators/attackers can obtain is constrained by the scheme requirements or the limited accessibility of the target. Even worse, various countermeasures in modern devices increase the conditions on the profiling size to break the target.
This work demonstrates a practical approach to dealing with the lack of profiling traces. Instead of learning from a one-hot encoded label, transferring the labels to their distribution can significantly speed up the convergence of guessing entropy. By studying the relationship between all possible key candidates, we propose a new metric, denoted Label Correlation (LC), to evaluate the generalization ability of the profiling model. We validate LC with two common use cases: early stopping and network architecture search, and the results indicate its superior performance.
## 2023/207
* Title: On Quantum Secure Compressing Pseudorandom Functions
* Authors: Ritam Bhaumik, Benoît Cogliati, Jordan Ethan, Ashwin Jha
* [Permalink](https://eprint.iacr.org/2023/207)
* [Download](https://eprint.iacr.org/2023/207.pdf)
### Abstract
In this paper we characterize all $2n$-bit-to-$n$-bit Pseudorandom Functions (PRFs) constructed with the minimum number of calls to $n$-bit-to-$n$-bit PRFs and arbitrary number of linear functions. First, we show that all two-round constructions are either classically insecure, or vulnerable to quantum period-finding attacks. Second, we categorize three-round constructions depending on their vulnerability to these types of attacks. This allows us to identify classes of constructions that could be proven secure. We then proceed to show the security of the following three candidates against any quantum distinguisher that asks at most $ 2^{n/4} $ (possibly superposition) queries
\[
\begin{array}{rcl}
\mathsf{TNT}(x_1,x_2) &:=& f_3(x_2 \oplus f_2(x_2 \oplus f_1(x_1)))\\
\mathsf{LRQ}(x_1,x_2) &:=& f_2(x_2) \oplus f_3(x_2 \oplus f_1(x_1))\\
\mathsf{LRWQ}(x_1,x_2) &:=& f_3( f_1(x_1) \oplus f_2(x_2)).
\end{array}
\]
Note that the first construction is a classically secure tweakable block cipher due to Bao et al., and the third construction is shown to be quantum secure tweakable block cipher by Hosoyamada and Iwata with similar query limits. Of note is our proof framework, an adaptation of Chung et al.'s rigorous formulation of Zhandry's compressed oracle technique in indistinguishability setup, which could be of independent interests. This framework gives very compact and mostly classical looking proofs as compared to Hosoyamada and Iwata interpretation of Zhandry's compressed oracle.
## 2023/549
* Title: Weak instances of class group action based cryptography via self-pairings
* Authors: Wouter Castryck, Marc Houben, Simon-Philipp Merz, Marzio Mula, Sam van Buuren, Frederik Vercauteren
* [Permalink](https://eprint.iacr.org/2023/549)
* [Download](https://eprint.iacr.org/2023/549.pdf)
### Abstract
In this paper we study non-trivial self-pairings with cyclic domains that are compatible with isogenies between elliptic curves oriented by an imaginary quadratic order $\mathcal{O}$. We prove that the order $m$ of such a self-pairing necessarily satisfies $m \mid \Delta_\mathcal{O}$ (and even $2m \mid \Delta_\mathcal{O} $ if $4 \mid \Delta_\mathcal{O}$ and $4m \mid \Delta_\mathcal{O}$ if $8 \mid \Delta_\mathcal{O}$) and is not a multiple of the field characteristic. Conversely, for each $m$ satisfying these necessary conditions, we construct a family of non-trivial cyclic self-pairings of order $m$ that are compatible with oriented isogenies, based on generalized Weil and Tate pairings.
As an application, we identify weak instances of class group actions on elliptic curves assuming the degree of the secret isogeny is known. More in detail, we show that if $m^2 \mid \Delta_\mathcal{O}$ for some prime power $m$ then given two primitively $\mathcal{O}$-oriented elliptic curves $(E, \iota)$ and $(E',\iota') = [\mathfrak{a}] (E,\iota)$ connected by an unknown invertible ideal $\mathfrak{a} \subseteq \mathcal{O}$, we can recover $\mathfrak{a}$ essentially at the cost of a discrete logarithm computation in a group of order $m^2$, assuming the norm of $\mathfrak{a}$ is given and is smaller than $m^2$. We give concrete instances, involving ordinary elliptic curves over finite fields, where this turns into a polynomial time attack.
Finally, we show that these self-pairings simplify known results on the decisional Diffie-Hellman problem for class group actions on oriented elliptic curves.
## 2023/757
* Title: A Note on ``On the Design of Mutual Authentication and Key Agreement Protocol in Internet of Vehicles-Enabled Intelligent Transportation System''
* Authors: Zhengjun Cao, Lihua Liu
* [Permalink](https://eprint.iacr.org/2023/757)
* [Download](https://eprint.iacr.org/2023/757.pdf)
### Abstract
We remark that the key agreement scheme [IEEE Trans. Veh. Technol. 2021, 70(2): 1736--1751] fails to keep anonymity and untraceability, because the user $U_k$ needs to invoke the public key $PK_{U_j}$ to verify the signature generated by the user $U_j$. Since the public key is compulsively linked to the true identity $ID_{U_j}$ for authentication, any adversary can reveal the true identity by checking the signature.
## 2023/758
* Title: Scaling Mobile Private Contact Discovery to Billions of Users
* Authors: Laura Hetz, Thomas Schneider, Christian Weinert
* [Permalink](https://eprint.iacr.org/2023/758)
* [Download](https://eprint.iacr.org/2023/758.pdf)
### Abstract
Mobile contact discovery is a convenience feature of messengers such as WhatsApp or Telegram that helps users to identify which of their existing contacts are registered with the service. Unfortunately, the contact discovery implementation of many popular messengers massively violates the users' privacy as demonstrated by Hagen et al. (NDSS '21, ACM TOPS '23). Unbalanced private set intersection (PSI) protocols are a promising cryptographic solution to realize mobile private contact discovery, however, state-of-the-art protocols do not scale to real-world database sizes with billions of registered users in terms of communication and/or computation overhead.
In our work, we make significant steps towards truly practical large-scale mobile private contact discovery. For this, we combine and substantially optimize the unbalanced PSI protocol of Kales et al. (USENIX Security '19) and the private information retrieval (PIR) protocol of Kogan and Corrigan-Gibbs (USENIX Security '21). Our resulting protocol has a total communication overhead that is sublinear in the size of the server's user database and also has sublinear online runtimes. We optimize our protocol by introducing database partitioning and efficient scheduling of user queries. To handle realistic change rates of databases and contact lists, we propose and evaluate different possibilities for efficient updates. We implement our protocol on smartphones and measure online runtimes of less than 2s to query up to 1024 contacts from a database with more than two billion entries. Furthermore, we achieve a reduction in setup communication up to factor 32x compared to state-of-the-art mobile private contact discovery protocols.
## 2023/759
* Title: Efficient TFHE Bootstrapping in the Multiparty Setting
* Authors: Jeongeun Park, Sergi Rovira
* [Permalink](https://eprint.iacr.org/2023/759)
* [Download](https://eprint.iacr.org/2023/759.pdf)
### Abstract
In this paper, we introduce a new approach to efficiently compute TFHE bootstrapping keys for (predefined) multiple users. Hence, a fixed number of users can enjoy the same level of efficiency as in the single key setting, keeping their individual input privacy. Our construction relies on a novel algorithm called homomorphic indicator, which can be of independent interest. We provide a detailed analysis of the noise growth and a set of secure parameters suitable to be used in practice. Moreover, we compare the complexity of our technique with other state-of-the-art constructions and show which method performs better in what parameter sets, based on our noise analysis. We also provide a prototype implementation of our technique. To the best of our knowledge, this is the first implementation of TFHE in the multiparty setting.
## 2023/760
* Title: Time to Bribe: Measuring Block Construction Market
* Authors: Anton Wahrstätter, Liyi Zhou, Kaihua Qin, Davor Svetinovic, Arthur Gervais
* [Permalink](https://eprint.iacr.org/2023/760)
* [Download](https://eprint.iacr.org/2023/760.pdf)
### Abstract
With the emergence of Miner Extractable Value (MEV), block construction markets on blockchains have evolved into a competitive arena. Following Ethereum's transition from Proof of Work (PoW) to Proof of Stake (PoS), the Proposer Builder Separation (PBS) mechanism has emerged as the dominant force in the Ethereum block construction market.
This paper presents an in-depth longitudinal study of the Ethereum block construction market, spanning from the introduction of PoS and PBS in September 2022 to May 2023. We analyze the market shares of builders and relays, their temporal changes, and the financial dynamics within the PBS system, including payments among builders and block proposers---commonly referred to as bribes. We introduce an MEV-time law quantifying the expected MEV revenue wrt. the time elapsed since the last proposed block. We provide empirical evidence that moments of crisis (e.g. the FTX collapse, USDC stablecoin de-peg) coincide with significant spikes in MEV payments compared to the baseline.
Despite the intention of the PBS architecture to enhance decentralization by separating actor roles, it remains unclear whether its design is optimal. Implicit trust assumptions and conflicts of interest may benefit particular parties and foster the need for vertical integration. MEV-Boost was explicitly designed to foster decentralization, causing the side effect of enabling risk-free sandwich extraction from unsuspecting users, potentially raising concerns for regulators.
## 2023/761
* Title: Nimble: Rollback Protection for Confidential Cloud Services (extended version)
* Authors: Sebastian Angel, Aditya Basu, Weidong Cui, Trent Jaeger, Stella Lau, Srinath Setty, Sudheesh Singanamalla
* [Permalink](https://eprint.iacr.org/2023/761)
* [Download](https://eprint.iacr.org/2023/761.pdf)
### Abstract
This paper introduces Nimble, a cloud service that helps applications running in trusted execution environments (TEEs) to detect rollback attacks (i.e., detect whether a data item retrieved from persistent storage is the latest version). To achieve this, Nimble realizes an append-only ledger service by employing a simple state machine running in a TEE in conjunction with a crash fault-tolerant storage service. Nimble then replicates this trusted state machine to ensure the system is available even if a minority of state machines crash. A salient aspect of Nimble is a new reconfiguration protocol that allows a cloud provider to replace the set of nodes running the trusted state machine whenever it wishes—without affecting safety. We have formally verified Nimble’s core protocol in Dafny, and have implemented Nimble such that its trusted state machine runs in multiple TEE platforms (Intel SGX and AMD SNP-SEV). Our results show that a deployment of Nimble on machines running in different availability zones can achieve from tens of thousands of requests/sec with an end-to-end latency of under 3.2 ms (based on an in-memory key-value store) to several thousands of requests/sec with a latency of 30ms (based on Azure Table).
## 2023/762
* Title: How to Design Fair Protocols in the Multi-Blockchain Setting
* Authors: Sivanarayana Gaddam, Ranjit Kumaresan, Srinivasan Raghuraman, Rohit Sinha
* [Permalink](https://eprint.iacr.org/2023/762)
* [Download](https://eprint.iacr.org/2023/762.pdf)
### Abstract
Recently, there have been several proposals for secure computation with fair output delivery that require the use of a bulletin board abstraction (in addition to a trusted execution environment (TEE)). These proposals require all protocol participants to have read/write access to the bulletin board. These works envision the use of (public or permissioned) blockchains to implement the bulletin board abstractions. With the advent of consortium blockchains which place restrictions on who can read/write contents on the blockchain, it is not clear how to extend prior proposals to a setting where (1) not all parties have read/write access on a single consortium blockchain, and (2) not all parties prefer to post on a public blockchain.
In this paper, we address the above by showing the first protocols for fair secure computation in the multi-blockchain setting. More concretely, in a $n$-party setting where at most $t < n$ parties are corrupt, our protocol for fair secure computation works as long as (1) $t$ parties have access to a TEE (e.g., Intel SGX), and (2) each of the above $t$ parties are on some blockchain with each of the other parties. Furthermore, only these $t$ parties need write access on the blockchains.
In an optimistic setting where parties behave honestly, our protocol runs completely off-chain.
## 2023/763
* Title: Undetectable Watermarks for Language Models
* Authors: Miranda Christ, Sam Gunn, Or Zamir
* [Permalink](https://eprint.iacr.org/2023/763)
* [Download](https://eprint.iacr.org/2023/763.pdf)
### Abstract
Recent advances in the capabilities of large language models such as GPT-4 have spurred increasing concern about our ability to detect AI-generated text. Prior works have suggested methods of embedding watermarks in model outputs, by $\textit{noticeably}$ altering the output distribution. We ask: Is it possible to introduce a watermark without incurring $\textit{any detectable}$ change to the output distribution?
To this end we introduce a cryptographically-inspired notion of undetectable watermarks for language models. That is, watermarks can be detected only with the knowledge of a secret key; without the secret key, it is computationally intractable to distinguish watermarked outputs from those of the original model. In particular, it is impossible for a user to observe any degradation in the quality of the text. Crucially, watermarks should remain undetectable even when the user is allowed to adaptively query the model with arbitrarily chosen prompts. We construct undetectable watermarks based on the existence of one-way functions, a standard assumption in cryptography.
## 2023/764
* Title: Subversion-Resilient Authenticated Encryption without Random Oracles
* Authors: Pascal Bemmann, Sebastian Berndt, Denis Diemert, Thomas Eisenbarth, Tibor Jager
* [Permalink](https://eprint.iacr.org/2023/764)
* [Download](https://eprint.iacr.org/2023/764.pdf)
### Abstract
In 2013, the Snowden revelations have shown subversion of cryptographic implementations to be a relevant threat.
Since then, the academic community has been pushing the development of models and constructions
to defend against adversaries able to arbitrarily subvert cryptographic implementations.
To capture these strong capabilities of adversaries, Russell, Tang, Yung, and Zhou (CCS'17) proposed CPA-secure encryption in a model that utilizes a trusted party called a watchdog testing an implementation before use to detect potential subversion.
This model was used to construct subversion-resilient implementations of primitives such as random oracles by Russell, Tang, Yung, and Zhou (CRYPTO'18) or signature schemes by Chow et al. (PKC'19) but primitives aiming for a CCA-like security remained elusive in any watchdog model.
In this work, we present the first subversion-resilient authenticated encryption scheme with associated data (AEAD) without making use of random oracles.
At the core of our construction are subversion-resilient PRFs, which we obtain from weak PRFs in combination with the classical Naor-Reingold transformation.
We revisit classical constructions based on PRFs to obtain subversion-resilient MACs, where both tagging and verification are subject to subversion, as well as subversion-resilient symmetric encryption in the form of stream ciphers.
Finally, we observe that leveraging the classical Encrypt-then-MAC approach yields subversion-resilient AEAD.
Our results are based on the trusted amalgamation model by Russell, Tang, Yung, and Zhou (ASIACRYPT'16) and the assumption of honest key generation.
## 2023/765
* Title: Threshold ECDSA in Three Rounds
* Authors: Jack Doerner, Yashvanth Kondi, Eysa Lee, abhi shelat
* [Permalink](https://eprint.iacr.org/2023/765)
* [Download](https://eprint.iacr.org/2023/765.pdf)
### Abstract
We present a three-round protocol for threshold ECDSA signing with malicious security against a dishonest majority, which information-theoretically UC-realizes a standard threshold signing functionality, assuming ideal commitment and two-party multiplication primitives. Our work improves upon and fully subsumes the DKLs $t$-of-$n$ and 2-of-$n$ protocols. This document focuses on providing a succinct but complete description of the protocol and its security proof, and contains little expository text.
## 2023/766
* Title: Lattice-based Commit-Transferrable Signatures and Applications to Anonymous Credentials
* Authors: Qiqi Lai, Feng-Hao Liu, Anna Lysyanskaya, Zhedong Wang
* [Permalink](https://eprint.iacr.org/2023/766)
* [Download](https://eprint.iacr.org/2023/766.pdf)
### Abstract
Anonymous Credentials are an important tool to protect user's privacy for proving possession of certain credentials.
Although various efficient constructions have been proposed based on pre-quantum assumptions, there have been limited accomplishments in the post-quantum and especially practical settings. This research aims to derive new methods that enhance the current state of the art.
To achieve this, we make the following contributions.
By distilling prior design insights, we propose a new primitive to instantiate \emph{signature with protocols}, called commit-transferrable signature (\CTS). When combined with a multi-theorem straight-line extractable non-interactive zero-knowledge proof of knowledge (\NIZKPoK), $\CTS$ gives a modular approach to construct anonymous credentials.
We then show efficient instantiations of $\CTS$ and the required \NIZKPoK from lattices, which are believed to be post-quantum hard. Finally, we propose concrete parameters for the $\CTS$, \NIZKPoK, and the overall Anonymous Credentials, based on Module-\SIS~and Ring-\LWE. This would serve as an important guidance for future deployment in practice.
## 2023/767
* Title: LFHE: Fully Homomorphic Encryption with Bootstrapping Key Size Less than a Megabyte
* Authors: Andrey Kim, Yongwoo Lee, Maxim Deryabin, Jieun Eom, Rakyong Choi
* [Permalink](https://eprint.iacr.org/2023/767)
* [Download](https://eprint.iacr.org/2023/767.pdf)
### Abstract
Fully Homomorphic Encryption (FHE) enables computations to be performed on encrypted data, so one can outsource computations of confidential information to an untrusted party. Ironically, FHE requires the client to generate massive evaluation keys and transfer them to the server side where all computations are supposed to be performed. In this paper, we propose LFHE, the Light-key FHE variant of the FHEW scheme introduced by Ducas and Micciancio in Eurocrypt 2015, and its improvement TFHE scheme proposed by Chillotti et al. in Asiacrypt 2016. In the proposed scheme the client generates small packed evaluation keys, which can be transferred to the server side with much smaller communication overhead compared to the original non-packed variant. The server employs a key reconstruction technique to obtain the evaluation keys needed for computations.
This approach allowed us to achieve the FHE scheme with the packed evaluation key transferring size of less than a Megabyte, which is an order of magnitude improvement compared to the best-known methods.
## 2023/768
* Title: Owl: An Augmented Password-Authenticated Key Exchange Scheme
* Authors: Feng Hao, Samiran Bag, Liqun Chen, Paul C. van Oorschot
* [Permalink](https://eprint.iacr.org/2023/768)
* [Download](https://eprint.iacr.org/2023/768.pdf)
### Abstract
We present Owl, an augmented password-authenticated key exchange (PAKE) protocol that is both efficient and supported by security proofs. Owl is motivated by recognized limitations in SRP-6a and OPAQUE. SRP-6a is the only augmented PAKE that has enjoyed wide use in practice to date, but it lacks the support of formal security proofs, and does not support elliptic curve settings. OPAQUE was proposed in 2018 as a provably secure and efficient alternative to SRP-6a, and was chosen by the IETF in 2020 for standardization, but open issues leave it unclear whether OPAQUE will replace SRP-6a in practice. Owl is obtained by efficiently adapting J-PAKE to an asymmetric setting, providing additional security against server compromise yet with lower computation than J-PAKE. Our scheme is provably secure, efficient and agile in supporting implementations in diverse multiplicative groups and elliptic curve settings. Owl is the first solution that provides systematic advantages over SRP-6a in terms of security, computation, message sizes, and agility. Owl’s agility across settings also contrasts ongoing issues related to how OPAQUE will instantiate a hash-to-curve operation in the elliptic curve setting (and what impact this will have on efficiency, security and forward compatibility with new elliptic curves in the future).
## 2023/769
* Title: Brakedown's expander code
* Authors: Ulrich Haböck
* [Permalink](https://eprint.iacr.org/2023/769)
* [Download](https://eprint.iacr.org/2023/769.pdf)
### Abstract
This write-up summarizes the sampling analysis of the expander code from Brakedown [GLSTW21]. We elaborate their convexity argument for general linear expansion bounds, and we combine their approach with the one from Spielman [Sp96] to achieve asymptotic linear-time under constant field size. Choosing tighter expansion bounds we obtain more efficient parameters than [GLSTW21] for their 128 bit large field, reducing the encoding costs by 25% and beyond, and we provide a similar parameter set for the Mersenne prime field with modulus $p = 2^{31} - 1$, optimized by the combined Spielman-Brakedown approach.
## 2023/770
* Title: Towards compressed permutation oracles
* Authors: Dominique Unruh
* [Permalink](https://eprint.iacr.org/2023/770)
* [Download](https://eprint.iacr.org/2023/770.pdf)
### Abstract
Compressed oracles (Zhandry, Crypto 2019) are a powerful technique to reason about quantum random oracles, enabling a sort of lazy sampling in the presence of superposition queries. A long-standing open question is whether a similar technique can also be used to reason about random (efficiently invertible) permutations.
In this work, we make a step towards answering this question. We first define the compressed permutation oracle and illustrate its use. While the soundness of this technique (i.e., the indistinguishability from a random permutation) remains a conjecture, we show a curious 2-for-1 theorem: If we use the compressed permutation oracle methodology to show that some construction (e.g., Luby-Rackoff) implements a random permutation (or strong qPRP), then we get the fact that this methodology is actually sound for free.
## 2023/771
* Title: Revisiting Key Decomposition Techniques for FHE: Simpler, Faster and More Generic
* Authors: Mariya Georgieva Belorgey, Sergiu Carpov, Nicolas Gama, Sandra Guasch, Dimitar Jetchev
* [Permalink](https://eprint.iacr.org/2023/771)
* [Download](https://eprint.iacr.org/2023/771.pdf)
### Abstract
Ring-LWE based homomorphic encryption computations in large depth use a combination of two techniques: 1) decomposition of big numbers into small limbs/digits, and 2) efficient cyclotomic multiplications modulo $X^N+1$. It was long believed that the two mechanisms had to be strongly related, like in the full-RNS setting that uses a CRT decomposition of big numbers over an NTT-friendly family of prime numbers, and NTT over the same primes for multiplications. However, in this setting NTT was the bottleneck of all large-depth FHE computations. A breakthrough result from Crypto'2023 by Kim et al. managed to overcome this limitation by introducing a second gadget decomposition and by showing that it indeed shifts the bottleneck and renders the cost of NTT computations negligible compared to the rest of the computation. In this paper, we extend this result (far) beyond the Full-RNS settings and show that we can completely decouple the big number decomposition from the cyclotomic arithmetic aspects. As a result, we get modulus switching/rescaling for free, and the memory footprint for storing relinearization keys across different levels is considerably lower compared to the CRT-based counterparts, by typically a factor $\ell/3$ where $\ell$ is the deepest level of multiplication depth supported. We verify both in theory and in practice that the performance of key-switching, external and internal products and automorphisms using our representation are similar or faster than the one achieved by Kim et al. Crypto'2023 paper, and we discuss the high impact of these results for people who work on low-level or hardware optimizations as well as the benefits of the new parametrizations for people currently working on compilers for FHE.
We even manage to lower the running time of the gate bootstrapping of TFHE by eliminating 12.5% of its FFTs.
## 2023/772
* Title: Classical and Quantum Meet-in-the-Middle Nostradamus Attacks on AES-like Hashing
* Authors: Zhiyu Zhang, Siwei Sun, Caibing Wang, Lei Hu
* [Permalink](https://eprint.iacr.org/2023/772)
* [Download](https://eprint.iacr.org/2023/772.pdf)
### Abstract
At EUROCRYPT 2006, Kelsey and Kohno proposed the so-called chosen target forced-prefix (CTFP) preimage attack, where for any challenge prefix $P$, the attacker can generate a suffix $S$ such that $H(P\|S) = y$ for some hash value $y$ published in advance by the attacker. Consequently, the attacker can pretend to predict some event represented by $P$ she did not know before, and thus this type of attack is also known as the Nostradamus attack. At ASIACRYPT 2022, Benedikt et al. convert Kelsey et al.'s attack to a quantum one, reducing the time complexity from $\mathcal{O}(\sqrt{n}\cdot 2^{2n/3})$ to $\mathcal{O}(\sqrt[3]{n} \cdot 2^{3n/7})$. CTFP preimage attack is less investigated in the literature than (second-)preimage and collision attacks and lacks dedicated methods. In this paper, we propose the first dedicated Nostradamus attack based on the meet-in-the-middle (MITM) attack, and the MITM Nostradamus attack could be up to quadratically accelerated in the quantum setting. According to the recent works on MITM preimage attacks on AES-like hashing, we build an automatic tool to search for optimal MITM Nostradamus attacks and model the tradeoff between the offline and online phases. We apply our method to AES-MMO and Whirlpool, and obtain the first dedicated attack on round-reduced version of these hash functions. Our method and automatic tool are applicable to other AES-like hashings.
## 2023/773
* Title: An update on Keccak performance on ARMv7-M
* Authors: Alexandre Adomnicai
* [Permalink](https://eprint.iacr.org/2023/773)
* [Download](https://eprint.iacr.org/2023/773.pdf)
### Abstract
This note provides an update on Keccak performance on the ARMv7-M processors. Starting from the XKCP implementation, we have applied architecture-specific optimizations that have yielded a performance gain of up to 21% for the largest permutation instance.
## 2023/774
* Title: Tagged Chameleon Hash from Lattice and Application to Redactable Blockchain
* Authors: Yiming Li, Shengli Liu
* [Permalink](https://eprint.iacr.org/2023/774)
* [Download](https://eprint.iacr.org/2023/774.pdf)
### Abstract
Chameleon hash (CH) is a trapdoor hash function. Generally it is hard to find collisions, but with the help of trapdoor, finding collisions becomes easy. CH plays an important role in converting a conventional blockchain to a redactable one. However, most of the existing CH schemes are too weak to support redactable blockchain. The currently known CH schemes serving for redactable blockchain have the best security of so-called “full collision resistance (f-CR)”, but they are built either on random oracle model or rely on heavy tools like the simulation-sound extractable non-interactive zero-knowledge (SSE-NIZK) proof system. Moreover, up to now there is no CH scheme with post-quantum f-CR security in the standard model. Therefore, no CH can support redactable blockchain in a post-quantum way without relying on random oracles.
In this paper, we introduce a variant of CH, namely tagged chameleon hash (tCH). Tagged chameleon hash takes a tag into hash evaluations and collision finding algorithms. We define two security notions for tCH, collision resistance (CR) and full collision resistance (f-CR), and prove the equivalence between CR and f-CR when tCH works in the one-time tag mode. We propose a tCH scheme from lattice without using any NIZK proof, and prove that its collision resistance is (almost) tightly reduced to the Short Integer Solution (SIS) assumption in the standard model. We also show how to apply tCH to a blockchain in one-time tag mode so that the blockchain can be compiled to a redactable one. Our tCH scheme provides the first post-quantum solution for redactable blockchains, without resorting to random oracles or NIZK proofs. Besides, we also construct a more efficient tCH scheme with CR tightly reduced to SIS in the random oracle model, which may be of independent interest.
## 2023/775
* Title: Exact Security Analysis of ASCON
* Authors: Bishwajit Chakraborty, Chandranan Dhar, Mridul Nandi
* [Permalink](https://eprint.iacr.org/2023/775)
* [Download](https://eprint.iacr.org/2023/775.pdf)
### Abstract
The Ascon cipher suite, offering both authenticated encryption with associated data (AEAD) and hashing functionality, has recently emerged as the winner of the NIST Lightweight Cryptography (LwC) standardization process. The AEAD schemes within Ascon, namely Ascon-128 and Ascon-128a, have also been previously selected as the preferred lightweight authenticated encryption solutions in the CAESAR competition. In this paper, we present a tight and comprehensive security analysis of the Ascon AEAD schemes within the random permutation model. Existing integrity analyses of Ascon (and any Duplex AEAD scheme in general) commonly include the term $DT/2^c$, where $D$ and $T$ represent data and time complexities respectively, and $c$ denotes the capacity of the underlying sponge. In this paper, we demonstrate that Ascon achieves AE security when $T$ is bounded by $\min\{2^{\kappa}, 2^c\}$ (where $\kappa$ is the key size), and $DT$ is limited to $2^b$ (with $b$ being the size of the underlying permutation, which is 320 for Ascon). Our findings indicate that in accordance with NIST requirements, Ascon allows for a tag size as low as 64 bits while enabling a higher rate of 192 bits, surpassing the recommended rate.
## 2023/776
* Title: Quantum Attacks on Type-1 Generalized Feistel Schemes
* Authors: Hong-Wei Sun, Bin-Bin Cai, Su-Juan Qin, Qiao-Yan Wen, Fei Gao
* [Permalink](https://eprint.iacr.org/2023/776)
* [Download](https://eprint.iacr.org/2023/776.pdf)
### Abstract
Generalized Feistel schemes (GFSs) are extremely important and extensively researched cryptographic schemes. In this paper, we investigate the security of Type-1 GFS in quantum circumstances. On the one hand, in the qCCA setting, we give a new quantum polynomial time distinguisher on (d^2 -1)-round Type-1 GFS with branches d >3, which extends the previous results by d-2 rounds. This leads to a more efficient analysis of type-1 GFS, that is, the complexity of some previous key-recovery attacks is reduced by a factor of 2^(((d-2)k)/2), where k is the key length of the internal round function. On the other hand, for CAST-256, which is a certain block cipher based on Type-1 GFS, we give a 17-round quantum distinguisher in the qCPA setting. As a result, we construct an r(r > 17) round quantum key-recovery attack with complexity O(2^(37(r-17))/2 ).
## 2023/777
* Title: Too Many Hints - When LLL Breaks LWE
* Authors: Alexander May, Julian Nowakowski
* [Permalink](https://eprint.iacr.org/2023/777)
* [Download](https://eprint.iacr.org/2023/777.pdf)
### Abstract
All modern lattice-based schemes build on variants of the LWE problem. Information leakage of the LWE secret $\mathbf s \in \mathbb{Z}_q^n$ is usually modeled via so-called hints, i.e., inner products of $\mathbf s$ with some (random, but known) vector.
At Crypto`20, Dachman-Soled, Ducas, Gong and Rossi (DDGR) defined among other so-called perfect hints and modular hints. The trailblazing DDGR framework allows to integrate and combine hints successively into lattices, and estimates the resulting LWE security loss.
We introduce a new methodology to integrate and combine an arbitrary number of perfect and modular in a single stroke. As opposed to DDGR, our methodology is significantly more efficient in constructing lattice bases, and thus easily allows for a large number of hints up to cryptographic dimensions, a regime that is impractical in DDGR. The efficiency of our method defines a large LWE parameter regime, in which we can fully carry out attacks faster than DDGR can solely estimate them. A key component of our new method is dimension reduction of $\mathbf s$, which significantly reduces LWE security.
The benefits of our approach allow us to practically determine which number of hints is sufficient to efficiently break LWE-based lattice schemes in practice. For mod-$q$ hints, i.e., modular hints defined over $\mathbb{Z}_q$, we reconstruct Kyber-512 secret keys via LLL reduction (only!) with an amount of $449$ hints. For Falcon-512, NTRU-HRSS-701, Kyber-768 and Dilithium-1024 we need $452$, $622$, $702$ and $876$ modular hints, respectively.
Our results for perfect hints significantly improve over these numbers, requiring for LWE dimension $n$ roughly $n/2$ perfect hints. Namely, we reconstruct via LLL reduction Kyber-512 keys with merely $234$ perfect hints. For secret keys of Falcon-512, NTRU-HRSS-701, Kyber-768 and Dilithium-1024 we require $233$, $332$, $390$ and $463$ perfect hints, respectively. We find such a small amount of perfect hints quite remarkable. If we resort to stronger lattice reduction techniques like BKZ, we need even fewer hints.
For mod-$q$ hints our method is extremely efficient, taking total time for constructing our lattice bases and secret key recovery via LLL of around 20 mins for dimension 512, 40 mins for dimensions 701 and 768, and less than 10 hours for dimension 1024. For perfect hints we require around 3 hours (dim 512), 11 hours (dim 701), 1 day (dim 768), and one week (dim 1024).
Our results demonstrate that especially perfect hints are powerful in practice, and stress the necessity to properly protect lattice schemes against leakage.
## 2023/778
* Title: Bounded Verification for Finite-Field-Blasting (In a Compiler for Zero Knowledge Proofs)
* Authors: Alex Ozdemir, Riad S. Wahby, Fraser Brown, Clark Barrett
* [Permalink](https://eprint.iacr.org/2023/778)
* [Download](https://eprint.iacr.org/2023/778.pdf)
### Abstract
Zero Knowledge Proofs (ZKPs) are cryptographic protocols
by which a prover convinces a verifier of the truth of a statement with-
out revealing any other information. Typically, statements are expressed
in a high-level language and then compiled to a low-level representation
on which the ZKP operates. Thus, a bug in a ZKP compiler can com-
promise the statement that the ZK proof is supposed to establish. This
paper takes a step towards ZKP compiler correctness by partially veri-
fying a field-blasting compiler pass, a pass that translates Boolean and
bit-vector logic into equivalent operations in a finite field. First, we define
correctness for field-blasters and ZKP compilers more generally. Next, we
describe the specific field-blaster using a set of encoding rules and de-
fine verification conditions for individual rules. Finally, we connect the
rules and the correctness definition by showing that if our verification
conditions hold, the field-blaster is correct. We have implemented our
approach in the CirC ZKP compiler and have proved bounded versions
of the corresponding verification conditions. We show that our partially
verified field-blaster does not hurt the performance of the compiler or its
output; we also report on four bugs uncovered during verification.
## 2023/779
* Title: Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the Cryptanalysis of pSIDH
* Authors: Mingjie Chen, Muhammad Imran, Gábor Ivanyos, Péter Kutas, Antonin Leroux, Christophe Petit
* [Permalink](https://eprint.iacr.org/2023/779)
* [Download](https://eprint.iacr.org/2023/779.pdf)
### Abstract
The Isogeny to Endomorphism Ring Problem (IsERP) asks to compute the endomorphism ring of the codomain of an isogeny between supersingular curves in characteristic $p$ given only a representation for this isogeny, i.e. some data and an algorithm to evaluate this isogeny on any torsion point. This problem plays a central role in isogeny-based cryptography; it underlies the security of
pSIDH protocol (ASIACRYPT 2022) and it is at the heart of the recent attacks that broke the SIDH key exchange. Prior to this work, no efficient algorithm was known to solve IsERP for a generic isogeny degree, the hardest case seemingly when the degree is prime.
In this paper, we introduce a new quantum polynomial-time algorithm to solve IsERP for isogenies whose degrees are odd and have $O(\log\log p)$ many prime factors. As main technical tools, our algorithm uses a quantum algorithm for computing hidden Borel subgroups, a group action on supersingular isogenies from EUROCRYPT 2021, various algorithms for the Deuring correspondence and a new algorithm to lift arbitrary quaternion order elements modulo an odd integer $N$ with $O(\log\log p)$ many prime factors to powersmooth elements.
As a main consequence for cryptography, we obtain a quantum polynomial-time key recovery attack on pSIDH. The technical tools we use may also be of independent interest.
## 2023/780
* Title: An Anonymous Multi-receiver Certificateless Hybrid Signcryption (AMCLHS) using mKEM-DEM for Broadcast Communication
* Authors: Alia Umrani, Apurva K Vangujar, Paolo Palmieri
* [Permalink](https://eprint.iacr.org/2023/780)
* [Download](https://eprint.iacr.org/2023/780.pdf)
### Abstract
Confidentiality, authentication, and anonymity are the fundamental security requirements in broadcast communication that can be achieved by Digital Signature (DS), encryption, and pseudo-anonymous identity techniques. Signcryption offer both DS and encryption in a single logical step with high efficiency. Similarly, anonymous multireceiver signcryption ensure receiver privacy by generating identical ciphertext for multiple receivers while keeping their identities private. While signcryption is a significant improvement over “sign then encrypt”, it still incurs higher computational and communication cost and does not provide the required level of security.
In this paper, we propose a multiple-recipient Key Encapsulation Mechanism (mKEM) - Data Encapsulation Mechanism (DEM) based Anonymous Multireceiver Certificateless Hybrid Signcryption (AMCLHS). The AMCLHS uses a combination of symmetric key and asymmetric key cryptography to signcrypt an arbitrary length message in broadcast communication and has two unique settings as follows:
Pseudo-Identity PID Settings: We introduce a new algorithmic step in AMCLHS construction where each user (sender and receiver) is assigned a PID to enable the sender to signcrypt identical messages for multiple receivers while keeping the identities of other receivers anonymous.
The receiver anonymity is achieved by choosing random Real-Identity (ID_R) to generate PID of the users in key generation algorithm of AMCLHS scheme. Our approach relies on the Elliptic Curve Discrete Logarithm (ECDL) hardness assumptions, the hash function, and verification-based secret key of the Register Authority (RA), using time Delta T.
mKEM-DEM Settings: We introduce the first construction that achieves optimal ciphertext from the Diffie-Hellman (DH) assumption using mKEM-DEM for Signcryption. Our scheme uses mKEM to generate a symmetric key for multiple-receivers and DEM to signcrypt message using the previously generated symmetric key and the sender's private key. mKEM for key setup and Signcryption for confidentiality and forward security, and DEM for key generation and unsigncryption for indistinguishability under Indistinguishability against Chosen Ciphertext Attack (IND-CCA2).
Our scheme relies on DH and Bilinear Pairing (BP) assumption and uses a single key for all messages, which minimizes ciphertext length and ultimately reduces complexity overhead.
The scheme operates in a multireceiver certificateless environment, preventing the key escrow problem, and demonstrates cryptographic notions for Indistinguishability under Chosen-Ciphertext Attack (IND-CCA2) and Existential Unforgeability against Chosen Message Attack (EUF-CMA) for Type-I and Type-II adversaries under q-Decisional Bilinear Diffie-Hellman Inversion (q-DBDHI) and ECDL hard assumptions. We compare the proposed scheme with existing multireceiver hybrid signcryption schemes in terms of computation cost, communication cost, and security requirements. We show that, compared to existing multireceiver schemes which has overall cost of O(n^2), our scheme is computationally more efficient and has optimal communication cost, with signcryption cost linear O(n) to the number of designated receivers while the unsigncryption cost remains constant O(1). Our scheme achieves confidentiality, authentication, anonymity, and simultaneously achieves unlinkability, non-repudiation, and forward security.
## 2023/781
* Title: $\mathsf{Skye}$: A Fast KDF based on Expanding PRF and its Application to Signal
* Authors: Amit Singh Bhati, Antonin Dufka, Elena Andreeva, Arnab Roy, Bart Preneel
* [Permalink](https://eprint.iacr.org/2023/781)
* [Download](https://eprint.iacr.org/2023/781.pdf)
### Abstract
A Key Derivation Function KDF generates a uniform and highly random key-stream from weakly random key material. KDFs are broadly used in various security protocols such as digital signatures and key exchange protocols. HKDF is the most deployed KDF in practice. It is based on the $\textit{extract-then-expand}$ paradigm and is presently used, among others, in the Signal Protocol for end-to-end encrypted messaging.
HKDF was proposed as a generic KDF for general input sources and thus is not optimized for source-specific use cases such as key derivation from Diffie-Hellman (DH) sources (i.e. DH shared secrets as key material). Furthermore, the sequential HKDF design is unnecessarily slower on some general-purpose platforms that benefit from parallelization.
In this work, we propose a novel, efficient and secure KDF called $\mathsf{Skye}$. $\mathsf{Skye}$ follows the $\textit{extract-then-expand}$ paradigm and consists of two algorithms: efficient deterministic $\textit{randomness extractor}$ and $\textit{expansion}$ functions. Instantiating our extractor for dedicated source-specific (e.g. DH sources) inputs allows us to achieve a significant efficiency speed-up over HKDF at the same security level. We provide concrete security analysis of $\mathsf{Skye}$ and both its algorithms in the standard model.
We provide a software performance comparison of $\mathsf{Skye}$ with the AES-based expanding PRF $\mathsf{ButterKnife}$ and HKDF with SHA-256 (as used in Signal). Our results show that in isolation $\mathsf{Skye}$ performs from 4x to 47x faster than HKDF, depending on the platform instruction support. We further demonstrate that with such a performance gain, when $\mathsf{Skye}$ is integrated within the current Signal implementation, we can achieve significant overall improvements ranging from $38\%$ to $64\%$ relative speedup in unidirectional messaging. Even in bidirectional messaging, that includes DH computation with dominating computational cost, $\mathsf{Skye}$ still contributes to $12-36\%$ relative speedup when just 10 messages are sent and received at once.
## 2023/782
* Title: Coefficient Grouping for Complex Affine Layers
* Authors: Fukang Liu, Lorenzo Grassi, Clémence Bouvier, Willi Meier, Takanori Isobe
* [Permalink](https://eprint.iacr.org/2023/782)
* [Download](https://eprint.iacr.org/2023/782.pdf)
### Abstract
Designing symmetric-key primitives for applications in Fully Homomorphic Encryption (FHE) has become important to address the issue of the ciphertext expansion. In such a context, cryptographic primitives with a low-AND-depth decryption circuit are desired. Consequently, quadratic nonlinear functions are commonly used in these primitives, including the well-known $\chi$ function over $\mathbb{F}_2^n$ and the power map over a large finite field $\mathbb{F}_{p^n}$. In this work, we study the growth of the algebraic degree for an SPN cipher over $\mathbb{F}_{2^n}^{m}$, whose S-box is defined as the combination of a power map $x\mapsto x^{2^d+1}$ and an $\mathbb{F}_2$-linearized affine polynomial $x\mapsto c_0+\sum_{i=1}^{w}c_ix^{2^{h_i}}$ where $c_1,\ldots,c_w\neq0$. Specifically, motivated by the fact that the original coefficient grouping technique published at EUROCRYPT 2023 becomes less efficient for $w>1$, we develop a variant technique that can efficiently work for arbitrary $w$. With this new technique to study the upper bound of the algebraic degree, we answer the following questions from a theoretic perspective:
1. can the algebraic degree increase exponentially when $w=1$?
2. what is the influence of $w$, $d$ and $(h_1,\ldots,h_w)$ on the growth of the algebraic degree?
Based on this, we show (i) how to efficiently find $(h_1,\ldots,h_w)$ to achieve the exponential growth of the algebraic degree and (ii) how to efficiently compute the upper bound of the algebraic degree for arbitrary $(h_1,\ldots,h_w)$. Therefore, we expect that these results can further advance the understanding of the design and analysis of such primitives.
## 2023/783
* Title: Breaking the power-of-two barrier: noise estimation for BGV in NTT-friendly rings
* Authors: Andrea Di Giusto, Chiara Marcolla
* [Permalink](https://eprint.iacr.org/2023/783)
* [Download](https://eprint.iacr.org/2023/783.pdf)
### Abstract
The Brakerski-Gentry-Vaikuntanathan (BGV) scheme is a Fully Homomorphic Encryption (FHE) cryptosystem based on the Ring Learning With Error (RLWE) problem.
Ciphertexts in this scheme contain an error term that grows with operations and causes decryption failure when it surpasses a certain threshold.
For this reason, the parameters of BGV need to be estimated carefully, with a trade-off between security and error margin.
The ciphertext space of BGV is the ring $\mathcal R_q=\mathbb Z_q[x]/(\Phi_m(x))$, where usually the degree $n$ of the cyclotomic polynomial $\Phi_m(x)$ is chosen as a power of two for efficiency reasons. However, the jump between two consecutive powers-of-two polynomials can sometimes also cause a jump of the security, resulting in parameters that are much bigger than what is needed.
In this work, we explore the non-power-of-two instantiations of BGV.
Although our theoretical research encompasses results applicable to any cyclotomic ring, our main investigation is focused on the case of $m=2^s 3^t$, i.e., cyclotomic polynomials with degree $n=2^s 3^{t-1}$.
We provide a thorough analysis of the noise growth in this new setting using the canonical norm and compare our results with the power-of-two case considering practical aspects like NTT algorithms.
We find that in many instances, the parameter estimation process yields better results for the non-power-of-two setting.
## 2023/784
* Title: History-Free Sequential Aggregate Signatures from Generic Trapdoor Functions
* Authors: Alessio Meneghetti, Edoardo Signorini
* [Permalink](https://eprint.iacr.org/2023/784)
* [Download](https://eprint.iacr.org/2023/784.pdf)
### Abstract
A sequential aggregate signature (SAS) scheme allows multiple users to sequentially combine their respective signatures in order to reduce communication costs. Historically, early proposals required the use of trapdoor permutation (e.g., RSA).
In recent years, a number of attempts have been made to extend SAS schemes to post-quantum assumptions. Many post-quantum signatures have been proposed in the hash-and-sign paradigm, which requires the use of trapdoor functions and appears to be an ideal candidate for sequential aggregation attempts. However, the hardness in achieving post-quantum one-way permutations makes it difficult to obtain similarly general constructions. Direct attempts at generalizing permutation-based schemes have been proposed, but they either lack formal security or require additional properties on the trapdoor function, which are typically not available for multivariate or code-based functions.
In this paper, we propose a history-free sequential aggregate signature based on generic trapdoor functions, generalizing existing techniques. We prove the security of our scheme in the random oracle model by adopting the probabilistic hash-and-sign with retry paradigm, and we instantiate our construction with three post-quantum schemes, comparing their compression capabilities. Finally, we discuss how direct extensions of permutation-based SAS schemes are not possible without additional properties, showing the insecurity of two existing multivariate schemes when instantiated with Unbalanced Oil and Vinegar.
## 2023/785
* Title: Generation of two ''independent'' points on an elliptic curve of $j$-invariant $\neq 0, 1728$
* Authors: Dmitrii Koshelev
* [Permalink](https://eprint.iacr.org/2023/785)
* [Download](https://eprint.iacr.org/2023/785.pdf)
### Abstract
This article is dedicated to a new generation method of two ``independent'' $\mathbb{F}_{\!q}$-points $P_0$, $P_1$ on almost any ordinary elliptic curve $E$ over a finite field $\mathbb{F}_{\!q}$ of large characteristic. In particular, the method is relevant for all standardized and real-world elliptic curves of $j$-invariants different from $0$, $1728$. The points $P_0$, $P_1$ are characterized by the fact that nobody (even a generator) knows the discrete logarithm $\log_{P_0}(P_1)$ in the group $E(\mathbb{F}_{\!q})$. Moreover, only one square root extraction in $\mathbb{F}_{\!q}$ (instead of two ones) is required in comparison with all previous generation methods.
## 2023/786
* Title: Blockchain Transaction Censorship: (In)secure and (In)efficient?
* Authors: Zhipeng Wang, Xihan Xiong, William J. Knottenbelt
* [Permalink](https://eprint.iacr.org/2023/786)
* [Download](https://eprint.iacr.org/2023/786.pdf)
### Abstract
The ecosystem around blockchain and Decentralized Finance (DeFi) is seeing more and more interest from centralized regulators. For instance, recently, the US government placed sanctions on the largest DeFi mixer, Tornado.Cash (TC). To our knowledge, this is the first time that centralized regulators sanction a decentralized and open-source blockchain application. It has led various blockchain participants, e.g., miners/validators and DeFi platforms, to censor TC-related transactions. The blockchain community has extensively discussed that censoring transactions could affect users’ privacy.
In this work, we analyze the efficiency and possible security implications of censorship on the different steps during the life cycle of a blockchain transaction, i.e., generation, propagation, and validation. We reveal that fine-grained censorship will reduce the security of block validators and centralized transaction propagation services, and can potentially cause Denial of Service (DoS) attacks. We also find that DeFi platforms adopt centralized third-party services to censor user addresses at the frontend level, which blockchain users could easily bypass. Moreover, we present a tainting attack whereby an adversary can prevent users from interacting normally with DeFi platforms by sending TC-related transactions.
## 2023/787
* Title: Private Proof-of-Stake Blockchains using Differentially-private Stake Distortion
* Authors: Chenghong Wang, David Pujo, Kartik Nayak, Ashwin Machanavajjhala
* [Permalink](https://eprint.iacr.org/2023/787)
* [Download](https://eprint.iacr.org/2023/787.pdf)
### Abstract
Safety, liveness, and privacy are three critical properties for any private proof-of-stake (PoS) blockchain. However, prior work (SP'21) has shown that to obtain safety and liveness, a PoS blockchain must in theory forgo privacy. Specifically, to ensure safety and liveness, PoS blockchains elect parties based on stake proportion, potentially exposing a party's stake even with private transaction processing. In this work, we make two key contributions. First, we present the first stake inference attack applicable to both deterministic and randomized PoS with exponentially less running time in comparison with SOTA designs. Second, we use differentially private stake distortion to achieve privacy in PoS blockchains and design two stake distortion mechanisms that any PoS protocol can use. We further evaluate our proposed methods using Ethereum 2.0, a widely-recognized PoS blockchain in operation. Results demonstrate effective stake inference risk mitigation, reasonable privacy, and preservation of essential safety and liveness properties.
## 2023/788
* Title: A flexible Snark via the monomial basis
* Authors: Steve Thakur
* [Permalink](https://eprint.iacr.org/2023/788)
* [Download](https://eprint.iacr.org/2023/788.pdf)
### Abstract
We describe a pairing-based SNARK with a universal updateable CRS that can be instantiated with any pairing-friendly curve endowed with a sufficiently large prime scalar field. We use the monomial basis, thus sidestepping the need for large smooth order subgroups in the scalar field. In particular, the scheme can be instantiated with outer curves to widely used curves such as Ed25519, secp256k1 and BN254. This allows us to largely circumvent the overhead of non-native field arithmetic for succinct proofs of statements in these base fields. These include proofs of valid signatures in Ed25519 and secp256k1 and one layer recursion with BN254.
The proof size is constant \( (10\; \mathbb{G}_1\), \(20\;\mathbb{F}_p)\), as is the verification runtime, which is dominated by a single pairing check (i.e. two pairings). The Prover time is dominated by the \(10\) multi-scalar multiplications in \(\mathbb{G}_1\) - with a combined MSM length of $22\cdot |\mathrm{Circuit}|$ - and, to a lesser extent, the computation of a single sum of polynomial products over the scalar field.
The scheme supports succinct lookup arguments for subsets as well as subsequences. Our construction relies on homomorphic table commitments, which makes them amenable to vector lookups. The Prover algorithm runs in runtime $O(M\cdot \log(M))$, where $M = \max \{|\text{Circuit}| , \;|\text{Table}|\}.$
When the scalar field has low $2$-adicity - as is inevitably the case with any outer curve to Ed25519, secp256k1 or BN254 - we use the Schonhage-Strassen algorithm or the multimodular FFT algorithm to compute the sum of polynomial products that occurs in one of the steps of the proof generation. Despite the small (but discernible) slowdown compared to polynomial products in FFT-friendly fields, we empirically found that the MSMs dominate the proof generation time. To that end, we have included some benchmarks for polynomial products in FFT-unfriendly fields.
Furthermore, the scheme supports custom gates, albeit at the cost of a larger proof size. As an application of the techniques in this paper, we describe a protocol that supports multiple \( \mathbf{univariate}\) custom gates $\mathcal{G}_i$ of high degree that are sparsely distributed, in the sense that \[ \sum_{i} \deg(\mathcal{G}_i)\cdot \#(\mathcal{G}_i\;\text{gates}) \; = \; O(|\text{Circuit}|). \] This comes at the cost of three additional $\mathbb{G}_1$ elements and does not blow up the proof generation time, i.e. it does not entail MSMs or FFTs of length larger than the circuit size.
At the moment, Panther Protocol's Rust implementation in a 576-bit pairing-friendly outer curve to Ed25519 has a (not yet optimized) Prover time of 45 seconds for a million gate circuit on a 64 vCPU AWS machine.
1. [2022/1332] On the Classic Protocol for MPC Schnorr Signatures
2. [2022/1507] Label Correlation in Deep Learning-based Side- ...
3. [2023/207] On Quantum Secure Compressing Pseudorandom Functions
4. [2023/549] Weak instances of class group action based ...
5. [2023/757] A Note on ``On the Design of Mutual Authentication ...
6. [2023/758] Scaling Mobile Private Contact Discovery to ...
7. [2023/759] Efficient TFHE Bootstrapping in the Multiparty Setting
8. [2023/760] Time to Bribe: Measuring Block Construction Market
9. [2023/761] Nimble: Rollback Protection for Confidential Cloud ...
10. [2023/762] How to Design Fair Protocols in the Multi- ...
11. [2023/763] Undetectable Watermarks for Language Models
12. [2023/764] Subversion-Resilient Authenticated Encryption ...
13. [2023/765] Threshold ECDSA in Three Rounds
14. [2023/766] Lattice-based Commit-Transferrable Signatures and ...
15. [2023/767] LFHE: Fully Homomorphic Encryption with ...
16. [2023/768] Owl: An Augmented Password-Authenticated Key ...
17. [2023/769] Brakedown's expander code
18. [2023/770] Towards compressed permutation oracles
19. [2023/771] Revisiting Key Decomposition Techniques for FHE: ...
20. [2023/772] Classical and Quantum Meet-in-the-Middle ...
21. [2023/773] An update on Keccak performance on ARMv7-M
22. [2023/774] Tagged Chameleon Hash from Lattice and Application ...
23. [2023/775] Exact Security Analysis of ASCON
24. [2023/776] Quantum Attacks on Type-1 Generalized Feistel Schemes
25. [2023/777] Too Many Hints - When LLL Breaks LWE
26. [2023/778] Bounded Verification for Finite-Field-Blasting (In ...
27. [2023/779] Hidden Stabilizers, the Isogeny To Endomorphism ...
28. [2023/780] An Anonymous Multi-receiver Certificateless Hybrid ...
29. [2023/781] $\mathsf{Skye}$: A Fast KDF based on Expanding PRF ...
30. [2023/782] Coefficient Grouping for Complex Affine Layers
31. [2023/783] Breaking the power-of-two barrier: noise estimation ...
32. [2023/784] History-Free Sequential Aggregate Signatures from ...
33. [2023/785] Generation of two ''independent'' points on an ...
34. [2023/786] Blockchain Transaction Censorship: (In)secure and ...
35. [2023/787] Private Proof-of-Stake Blockchains using ...
36. [2023/788] A flexible Snark via the monomial basis
## 2022/1332
* Title: On the Classic Protocol for MPC Schnorr Signatures
* Authors: Nikolaos Makriyannis
* [Permalink](https://eprint.iacr.org/2022/1332)
* [Download](https://eprint.iacr.org/2022/1332.pdf)
### Abstract
In this paper, we prove that the classic three-round protocol for MPC Schnorr Signatures is fully-adaptive UC-secure. Furthermore, we show that a simple variant of the Classic protocol achieves tight security, i.e.~the security of the resulting, modified, protocol tightly reduces to the security of the underlying non-MPC scheme.
## 2022/1507
* Title: Label Correlation in Deep Learning-based Side-channel Analysis
* Authors: Lichao Wu, Léo Weissbart, Marina Krček, Huimin Li, Guilherme Perin, Lejla Batina, Stjepan Picek
* [Permalink](https://eprint.iacr.org/2022/1507)
* [Download](https://eprint.iacr.org/2022/1507.pdf)
### Abstract
The efficiency of the profiling side-channel analysis can be significantly improved with machine learning techniques. Although powerful, a fundamental machine learning limitation of being data-hungry received little attention in the side-channel community. In practice, the maximum number of leakage traces that evaluators/attackers can obtain is constrained by the scheme requirements or the limited accessibility of the target. Even worse, various countermeasures in modern devices increase the conditions on the profiling size to break the target.
This work demonstrates a practical approach to dealing with the lack of profiling traces. Instead of learning from a one-hot encoded label, transferring the labels to their distribution can significantly speed up the convergence of guessing entropy. By studying the relationship between all possible key candidates, we propose a new metric, denoted Label Correlation (LC), to evaluate the generalization ability of the profiling model. We validate LC with two common use cases: early stopping and network architecture search, and the results indicate its superior performance.
## 2023/207
* Title: On Quantum Secure Compressing Pseudorandom Functions
* Authors: Ritam Bhaumik, Benoît Cogliati, Jordan Ethan, Ashwin Jha
* [Permalink](https://eprint.iacr.org/2023/207)
* [Download](https://eprint.iacr.org/2023/207.pdf)
### Abstract
In this paper we characterize all $2n$-bit-to-$n$-bit Pseudorandom Functions (PRFs) constructed with the minimum number of calls to $n$-bit-to-$n$-bit PRFs and arbitrary number of linear functions. First, we show that all two-round constructions are either classically insecure, or vulnerable to quantum period-finding attacks. Second, we categorize three-round constructions depending on their vulnerability to these types of attacks. This allows us to identify classes of constructions that could be proven secure. We then proceed to show the security of the following three candidates against any quantum distinguisher that asks at most $ 2^{n/4} $ (possibly superposition) queries
\[
\begin{array}{rcl}
\mathsf{TNT}(x_1,x_2) &:=& f_3(x_2 \oplus f_2(x_2 \oplus f_1(x_1)))\\
\mathsf{LRQ}(x_1,x_2) &:=& f_2(x_2) \oplus f_3(x_2 \oplus f_1(x_1))\\
\mathsf{LRWQ}(x_1,x_2) &:=& f_3( f_1(x_1) \oplus f_2(x_2)).
\end{array}
\]
Note that the first construction is a classically secure tweakable block cipher due to Bao et al., and the third construction is shown to be quantum secure tweakable block cipher by Hosoyamada and Iwata with similar query limits. Of note is our proof framework, an adaptation of Chung et al.'s rigorous formulation of Zhandry's compressed oracle technique in indistinguishability setup, which could be of independent interests. This framework gives very compact and mostly classical looking proofs as compared to Hosoyamada and Iwata interpretation of Zhandry's compressed oracle.
## 2023/549
* Title: Weak instances of class group action based cryptography via self-pairings
* Authors: Wouter Castryck, Marc Houben, Simon-Philipp Merz, Marzio Mula, Sam van Buuren, Frederik Vercauteren
* [Permalink](https://eprint.iacr.org/2023/549)
* [Download](https://eprint.iacr.org/2023/549.pdf)
### Abstract
In this paper we study non-trivial self-pairings with cyclic domains that are compatible with isogenies between elliptic curves oriented by an imaginary quadratic order $\mathcal{O}$. We prove that the order $m$ of such a self-pairing necessarily satisfies $m \mid \Delta_\mathcal{O}$ (and even $2m \mid \Delta_\mathcal{O} $ if $4 \mid \Delta_\mathcal{O}$ and $4m \mid \Delta_\mathcal{O}$ if $8 \mid \Delta_\mathcal{O}$) and is not a multiple of the field characteristic. Conversely, for each $m$ satisfying these necessary conditions, we construct a family of non-trivial cyclic self-pairings of order $m$ that are compatible with oriented isogenies, based on generalized Weil and Tate pairings.
As an application, we identify weak instances of class group actions on elliptic curves assuming the degree of the secret isogeny is known. More in detail, we show that if $m^2 \mid \Delta_\mathcal{O}$ for some prime power $m$ then given two primitively $\mathcal{O}$-oriented elliptic curves $(E, \iota)$ and $(E',\iota') = [\mathfrak{a}] (E,\iota)$ connected by an unknown invertible ideal $\mathfrak{a} \subseteq \mathcal{O}$, we can recover $\mathfrak{a}$ essentially at the cost of a discrete logarithm computation in a group of order $m^2$, assuming the norm of $\mathfrak{a}$ is given and is smaller than $m^2$. We give concrete instances, involving ordinary elliptic curves over finite fields, where this turns into a polynomial time attack.
Finally, we show that these self-pairings simplify known results on the decisional Diffie-Hellman problem for class group actions on oriented elliptic curves.
## 2023/757
* Title: A Note on ``On the Design of Mutual Authentication and Key Agreement Protocol in Internet of Vehicles-Enabled Intelligent Transportation System''
* Authors: Zhengjun Cao, Lihua Liu
* [Permalink](https://eprint.iacr.org/2023/757)
* [Download](https://eprint.iacr.org/2023/757.pdf)
### Abstract
We remark that the key agreement scheme [IEEE Trans. Veh. Technol. 2021, 70(2): 1736--1751] fails to keep anonymity and untraceability, because the user $U_k$ needs to invoke the public key $PK_{U_j}$ to verify the signature generated by the user $U_j$. Since the public key is compulsively linked to the true identity $ID_{U_j}$ for authentication, any adversary can reveal the true identity by checking the signature.
## 2023/758
* Title: Scaling Mobile Private Contact Discovery to Billions of Users
* Authors: Laura Hetz, Thomas Schneider, Christian Weinert
* [Permalink](https://eprint.iacr.org/2023/758)
* [Download](https://eprint.iacr.org/2023/758.pdf)
### Abstract
Mobile contact discovery is a convenience feature of messengers such as WhatsApp or Telegram that helps users to identify which of their existing contacts are registered with the service. Unfortunately, the contact discovery implementation of many popular messengers massively violates the users' privacy as demonstrated by Hagen et al. (NDSS '21, ACM TOPS '23). Unbalanced private set intersection (PSI) protocols are a promising cryptographic solution to realize mobile private contact discovery, however, state-of-the-art protocols do not scale to real-world database sizes with billions of registered users in terms of communication and/or computation overhead.
In our work, we make significant steps towards truly practical large-scale mobile private contact discovery. For this, we combine and substantially optimize the unbalanced PSI protocol of Kales et al. (USENIX Security '19) and the private information retrieval (PIR) protocol of Kogan and Corrigan-Gibbs (USENIX Security '21). Our resulting protocol has a total communication overhead that is sublinear in the size of the server's user database and also has sublinear online runtimes. We optimize our protocol by introducing database partitioning and efficient scheduling of user queries. To handle realistic change rates of databases and contact lists, we propose and evaluate different possibilities for efficient updates. We implement our protocol on smartphones and measure online runtimes of less than 2s to query up to 1024 contacts from a database with more than two billion entries. Furthermore, we achieve a reduction in setup communication up to factor 32x compared to state-of-the-art mobile private contact discovery protocols.
## 2023/759
* Title: Efficient TFHE Bootstrapping in the Multiparty Setting
* Authors: Jeongeun Park, Sergi Rovira
* [Permalink](https://eprint.iacr.org/2023/759)
* [Download](https://eprint.iacr.org/2023/759.pdf)
### Abstract
In this paper, we introduce a new approach to efficiently compute TFHE bootstrapping keys for (predefined) multiple users. Hence, a fixed number of users can enjoy the same level of efficiency as in the single key setting, keeping their individual input privacy. Our construction relies on a novel algorithm called homomorphic indicator, which can be of independent interest. We provide a detailed analysis of the noise growth and a set of secure parameters suitable to be used in practice. Moreover, we compare the complexity of our technique with other state-of-the-art constructions and show which method performs better in what parameter sets, based on our noise analysis. We also provide a prototype implementation of our technique. To the best of our knowledge, this is the first implementation of TFHE in the multiparty setting.
## 2023/760
* Title: Time to Bribe: Measuring Block Construction Market
* Authors: Anton Wahrstätter, Liyi Zhou, Kaihua Qin, Davor Svetinovic, Arthur Gervais
* [Permalink](https://eprint.iacr.org/2023/760)
* [Download](https://eprint.iacr.org/2023/760.pdf)
### Abstract
With the emergence of Miner Extractable Value (MEV), block construction markets on blockchains have evolved into a competitive arena. Following Ethereum's transition from Proof of Work (PoW) to Proof of Stake (PoS), the Proposer Builder Separation (PBS) mechanism has emerged as the dominant force in the Ethereum block construction market.
This paper presents an in-depth longitudinal study of the Ethereum block construction market, spanning from the introduction of PoS and PBS in September 2022 to May 2023. We analyze the market shares of builders and relays, their temporal changes, and the financial dynamics within the PBS system, including payments among builders and block proposers---commonly referred to as bribes. We introduce an MEV-time law quantifying the expected MEV revenue wrt. the time elapsed since the last proposed block. We provide empirical evidence that moments of crisis (e.g. the FTX collapse, USDC stablecoin de-peg) coincide with significant spikes in MEV payments compared to the baseline.
Despite the intention of the PBS architecture to enhance decentralization by separating actor roles, it remains unclear whether its design is optimal. Implicit trust assumptions and conflicts of interest may benefit particular parties and foster the need for vertical integration. MEV-Boost was explicitly designed to foster decentralization, causing the side effect of enabling risk-free sandwich extraction from unsuspecting users, potentially raising concerns for regulators.
## 2023/761
* Title: Nimble: Rollback Protection for Confidential Cloud Services (extended version)
* Authors: Sebastian Angel, Aditya Basu, Weidong Cui, Trent Jaeger, Stella Lau, Srinath Setty, Sudheesh Singanamalla
* [Permalink](https://eprint.iacr.org/2023/761)
* [Download](https://eprint.iacr.org/2023/761.pdf)
### Abstract
This paper introduces Nimble, a cloud service that helps applications running in trusted execution environments (TEEs) to detect rollback attacks (i.e., detect whether a data item retrieved from persistent storage is the latest version). To achieve this, Nimble realizes an append-only ledger service by employing a simple state machine running in a TEE in conjunction with a crash fault-tolerant storage service. Nimble then replicates this trusted state machine to ensure the system is available even if a minority of state machines crash. A salient aspect of Nimble is a new reconfiguration protocol that allows a cloud provider to replace the set of nodes running the trusted state machine whenever it wishes—without affecting safety. We have formally verified Nimble’s core protocol in Dafny, and have implemented Nimble such that its trusted state machine runs in multiple TEE platforms (Intel SGX and AMD SNP-SEV). Our results show that a deployment of Nimble on machines running in different availability zones can achieve from tens of thousands of requests/sec with an end-to-end latency of under 3.2 ms (based on an in-memory key-value store) to several thousands of requests/sec with a latency of 30ms (based on Azure Table).
## 2023/762
* Title: How to Design Fair Protocols in the Multi-Blockchain Setting
* Authors: Sivanarayana Gaddam, Ranjit Kumaresan, Srinivasan Raghuraman, Rohit Sinha
* [Permalink](https://eprint.iacr.org/2023/762)
* [Download](https://eprint.iacr.org/2023/762.pdf)
### Abstract
Recently, there have been several proposals for secure computation with fair output delivery that require the use of a bulletin board abstraction (in addition to a trusted execution environment (TEE)). These proposals require all protocol participants to have read/write access to the bulletin board. These works envision the use of (public or permissioned) blockchains to implement the bulletin board abstractions. With the advent of consortium blockchains which place restrictions on who can read/write contents on the blockchain, it is not clear how to extend prior proposals to a setting where (1) not all parties have read/write access on a single consortium blockchain, and (2) not all parties prefer to post on a public blockchain.
In this paper, we address the above by showing the first protocols for fair secure computation in the multi-blockchain setting. More concretely, in a $n$-party setting where at most $t < n$ parties are corrupt, our protocol for fair secure computation works as long as (1) $t$ parties have access to a TEE (e.g., Intel SGX), and (2) each of the above $t$ parties are on some blockchain with each of the other parties. Furthermore, only these $t$ parties need write access on the blockchains.
In an optimistic setting where parties behave honestly, our protocol runs completely off-chain.
## 2023/763
* Title: Undetectable Watermarks for Language Models
* Authors: Miranda Christ, Sam Gunn, Or Zamir
* [Permalink](https://eprint.iacr.org/2023/763)
* [Download](https://eprint.iacr.org/2023/763.pdf)
### Abstract
Recent advances in the capabilities of large language models such as GPT-4 have spurred increasing concern about our ability to detect AI-generated text. Prior works have suggested methods of embedding watermarks in model outputs, by $\textit{noticeably}$ altering the output distribution. We ask: Is it possible to introduce a watermark without incurring $\textit{any detectable}$ change to the output distribution?
To this end we introduce a cryptographically-inspired notion of undetectable watermarks for language models. That is, watermarks can be detected only with the knowledge of a secret key; without the secret key, it is computationally intractable to distinguish watermarked outputs from those of the original model. In particular, it is impossible for a user to observe any degradation in the quality of the text. Crucially, watermarks should remain undetectable even when the user is allowed to adaptively query the model with arbitrarily chosen prompts. We construct undetectable watermarks based on the existence of one-way functions, a standard assumption in cryptography.
## 2023/764
* Title: Subversion-Resilient Authenticated Encryption without Random Oracles
* Authors: Pascal Bemmann, Sebastian Berndt, Denis Diemert, Thomas Eisenbarth, Tibor Jager
* [Permalink](https://eprint.iacr.org/2023/764)
* [Download](https://eprint.iacr.org/2023/764.pdf)
### Abstract
In 2013, the Snowden revelations have shown subversion of cryptographic implementations to be a relevant threat.
Since then, the academic community has been pushing the development of models and constructions
to defend against adversaries able to arbitrarily subvert cryptographic implementations.
To capture these strong capabilities of adversaries, Russell, Tang, Yung, and Zhou (CCS'17) proposed CPA-secure encryption in a model that utilizes a trusted party called a watchdog testing an implementation before use to detect potential subversion.
This model was used to construct subversion-resilient implementations of primitives such as random oracles by Russell, Tang, Yung, and Zhou (CRYPTO'18) or signature schemes by Chow et al. (PKC'19) but primitives aiming for a CCA-like security remained elusive in any watchdog model.
In this work, we present the first subversion-resilient authenticated encryption scheme with associated data (AEAD) without making use of random oracles.
At the core of our construction are subversion-resilient PRFs, which we obtain from weak PRFs in combination with the classical Naor-Reingold transformation.
We revisit classical constructions based on PRFs to obtain subversion-resilient MACs, where both tagging and verification are subject to subversion, as well as subversion-resilient symmetric encryption in the form of stream ciphers.
Finally, we observe that leveraging the classical Encrypt-then-MAC approach yields subversion-resilient AEAD.
Our results are based on the trusted amalgamation model by Russell, Tang, Yung, and Zhou (ASIACRYPT'16) and the assumption of honest key generation.
## 2023/765
* Title: Threshold ECDSA in Three Rounds
* Authors: Jack Doerner, Yashvanth Kondi, Eysa Lee, abhi shelat
* [Permalink](https://eprint.iacr.org/2023/765)
* [Download](https://eprint.iacr.org/2023/765.pdf)
### Abstract
We present a three-round protocol for threshold ECDSA signing with malicious security against a dishonest majority, which information-theoretically UC-realizes a standard threshold signing functionality, assuming ideal commitment and two-party multiplication primitives. Our work improves upon and fully subsumes the DKLs $t$-of-$n$ and 2-of-$n$ protocols. This document focuses on providing a succinct but complete description of the protocol and its security proof, and contains little expository text.
## 2023/766
* Title: Lattice-based Commit-Transferrable Signatures and Applications to Anonymous Credentials
* Authors: Qiqi Lai, Feng-Hao Liu, Anna Lysyanskaya, Zhedong Wang
* [Permalink](https://eprint.iacr.org/2023/766)
* [Download](https://eprint.iacr.org/2023/766.pdf)
### Abstract
Anonymous Credentials are an important tool to protect user's privacy for proving possession of certain credentials.
Although various efficient constructions have been proposed based on pre-quantum assumptions, there have been limited accomplishments in the post-quantum and especially practical settings. This research aims to derive new methods that enhance the current state of the art.
To achieve this, we make the following contributions.
By distilling prior design insights, we propose a new primitive to instantiate \emph{signature with protocols}, called commit-transferrable signature (\CTS). When combined with a multi-theorem straight-line extractable non-interactive zero-knowledge proof of knowledge (\NIZKPoK), $\CTS$ gives a modular approach to construct anonymous credentials.
We then show efficient instantiations of $\CTS$ and the required \NIZKPoK from lattices, which are believed to be post-quantum hard. Finally, we propose concrete parameters for the $\CTS$, \NIZKPoK, and the overall Anonymous Credentials, based on Module-\SIS~and Ring-\LWE. This would serve as an important guidance for future deployment in practice.
## 2023/767
* Title: LFHE: Fully Homomorphic Encryption with Bootstrapping Key Size Less than a Megabyte
* Authors: Andrey Kim, Yongwoo Lee, Maxim Deryabin, Jieun Eom, Rakyong Choi
* [Permalink](https://eprint.iacr.org/2023/767)
* [Download](https://eprint.iacr.org/2023/767.pdf)
### Abstract
Fully Homomorphic Encryption (FHE) enables computations to be performed on encrypted data, so one can outsource computations of confidential information to an untrusted party. Ironically, FHE requires the client to generate massive evaluation keys and transfer them to the server side where all computations are supposed to be performed. In this paper, we propose LFHE, the Light-key FHE variant of the FHEW scheme introduced by Ducas and Micciancio in Eurocrypt 2015, and its improvement TFHE scheme proposed by Chillotti et al. in Asiacrypt 2016. In the proposed scheme the client generates small packed evaluation keys, which can be transferred to the server side with much smaller communication overhead compared to the original non-packed variant. The server employs a key reconstruction technique to obtain the evaluation keys needed for computations.
This approach allowed us to achieve the FHE scheme with the packed evaluation key transferring size of less than a Megabyte, which is an order of magnitude improvement compared to the best-known methods.
## 2023/768
* Title: Owl: An Augmented Password-Authenticated Key Exchange Scheme
* Authors: Feng Hao, Samiran Bag, Liqun Chen, Paul C. van Oorschot
* [Permalink](https://eprint.iacr.org/2023/768)
* [Download](https://eprint.iacr.org/2023/768.pdf)
### Abstract
We present Owl, an augmented password-authenticated key exchange (PAKE) protocol that is both efficient and supported by security proofs. Owl is motivated by recognized limitations in SRP-6a and OPAQUE. SRP-6a is the only augmented PAKE that has enjoyed wide use in practice to date, but it lacks the support of formal security proofs, and does not support elliptic curve settings. OPAQUE was proposed in 2018 as a provably secure and efficient alternative to SRP-6a, and was chosen by the IETF in 2020 for standardization, but open issues leave it unclear whether OPAQUE will replace SRP-6a in practice. Owl is obtained by efficiently adapting J-PAKE to an asymmetric setting, providing additional security against server compromise yet with lower computation than J-PAKE. Our scheme is provably secure, efficient and agile in supporting implementations in diverse multiplicative groups and elliptic curve settings. Owl is the first solution that provides systematic advantages over SRP-6a in terms of security, computation, message sizes, and agility. Owl’s agility across settings also contrasts ongoing issues related to how OPAQUE will instantiate a hash-to-curve operation in the elliptic curve setting (and what impact this will have on efficiency, security and forward compatibility with new elliptic curves in the future).
## 2023/769
* Title: Brakedown's expander code
* Authors: Ulrich Haböck
* [Permalink](https://eprint.iacr.org/2023/769)
* [Download](https://eprint.iacr.org/2023/769.pdf)
### Abstract
This write-up summarizes the sampling analysis of the expander code from Brakedown [GLSTW21]. We elaborate their convexity argument for general linear expansion bounds, and we combine their approach with the one from Spielman [Sp96] to achieve asymptotic linear-time under constant field size. Choosing tighter expansion bounds we obtain more efficient parameters than [GLSTW21] for their 128 bit large field, reducing the encoding costs by 25% and beyond, and we provide a similar parameter set for the Mersenne prime field with modulus $p = 2^{31} - 1$, optimized by the combined Spielman-Brakedown approach.
## 2023/770
* Title: Towards compressed permutation oracles
* Authors: Dominique Unruh
* [Permalink](https://eprint.iacr.org/2023/770)
* [Download](https://eprint.iacr.org/2023/770.pdf)
### Abstract
Compressed oracles (Zhandry, Crypto 2019) are a powerful technique to reason about quantum random oracles, enabling a sort of lazy sampling in the presence of superposition queries. A long-standing open question is whether a similar technique can also be used to reason about random (efficiently invertible) permutations.
In this work, we make a step towards answering this question. We first define the compressed permutation oracle and illustrate its use. While the soundness of this technique (i.e., the indistinguishability from a random permutation) remains a conjecture, we show a curious 2-for-1 theorem: If we use the compressed permutation oracle methodology to show that some construction (e.g., Luby-Rackoff) implements a random permutation (or strong qPRP), then we get the fact that this methodology is actually sound for free.
## 2023/771
* Title: Revisiting Key Decomposition Techniques for FHE: Simpler, Faster and More Generic
* Authors: Mariya Georgieva Belorgey, Sergiu Carpov, Nicolas Gama, Sandra Guasch, Dimitar Jetchev
* [Permalink](https://eprint.iacr.org/2023/771)
* [Download](https://eprint.iacr.org/2023/771.pdf)
### Abstract
Ring-LWE based homomorphic encryption computations in large depth use a combination of two techniques: 1) decomposition of big numbers into small limbs/digits, and 2) efficient cyclotomic multiplications modulo $X^N+1$. It was long believed that the two mechanisms had to be strongly related, like in the full-RNS setting that uses a CRT decomposition of big numbers over an NTT-friendly family of prime numbers, and NTT over the same primes for multiplications. However, in this setting NTT was the bottleneck of all large-depth FHE computations. A breakthrough result from Crypto'2023 by Kim et al. managed to overcome this limitation by introducing a second gadget decomposition and by showing that it indeed shifts the bottleneck and renders the cost of NTT computations negligible compared to the rest of the computation. In this paper, we extend this result (far) beyond the Full-RNS settings and show that we can completely decouple the big number decomposition from the cyclotomic arithmetic aspects. As a result, we get modulus switching/rescaling for free, and the memory footprint for storing relinearization keys across different levels is considerably lower compared to the CRT-based counterparts, by typically a factor $\ell/3$ where $\ell$ is the deepest level of multiplication depth supported. We verify both in theory and in practice that the performance of key-switching, external and internal products and automorphisms using our representation are similar or faster than the one achieved by Kim et al. Crypto'2023 paper, and we discuss the high impact of these results for people who work on low-level or hardware optimizations as well as the benefits of the new parametrizations for people currently working on compilers for FHE.
We even manage to lower the running time of the gate bootstrapping of TFHE by eliminating 12.5% of its FFTs.
## 2023/772
* Title: Classical and Quantum Meet-in-the-Middle Nostradamus Attacks on AES-like Hashing
* Authors: Zhiyu Zhang, Siwei Sun, Caibing Wang, Lei Hu
* [Permalink](https://eprint.iacr.org/2023/772)
* [Download](https://eprint.iacr.org/2023/772.pdf)
### Abstract
At EUROCRYPT 2006, Kelsey and Kohno proposed the so-called chosen target forced-prefix (CTFP) preimage attack, where for any challenge prefix $P$, the attacker can generate a suffix $S$ such that $H(P\|S) = y$ for some hash value $y$ published in advance by the attacker. Consequently, the attacker can pretend to predict some event represented by $P$ she did not know before, and thus this type of attack is also known as the Nostradamus attack. At ASIACRYPT 2022, Benedikt et al. convert Kelsey et al.'s attack to a quantum one, reducing the time complexity from $\mathcal{O}(\sqrt{n}\cdot 2^{2n/3})$ to $\mathcal{O}(\sqrt[3]{n} \cdot 2^{3n/7})$. CTFP preimage attack is less investigated in the literature than (second-)preimage and collision attacks and lacks dedicated methods. In this paper, we propose the first dedicated Nostradamus attack based on the meet-in-the-middle (MITM) attack, and the MITM Nostradamus attack could be up to quadratically accelerated in the quantum setting. According to the recent works on MITM preimage attacks on AES-like hashing, we build an automatic tool to search for optimal MITM Nostradamus attacks and model the tradeoff between the offline and online phases. We apply our method to AES-MMO and Whirlpool, and obtain the first dedicated attack on round-reduced version of these hash functions. Our method and automatic tool are applicable to other AES-like hashings.
## 2023/773
* Title: An update on Keccak performance on ARMv7-M
* Authors: Alexandre Adomnicai
* [Permalink](https://eprint.iacr.org/2023/773)
* [Download](https://eprint.iacr.org/2023/773.pdf)
### Abstract
This note provides an update on Keccak performance on the ARMv7-M processors. Starting from the XKCP implementation, we have applied architecture-specific optimizations that have yielded a performance gain of up to 21% for the largest permutation instance.
## 2023/774
* Title: Tagged Chameleon Hash from Lattice and Application to Redactable Blockchain
* Authors: Yiming Li, Shengli Liu
* [Permalink](https://eprint.iacr.org/2023/774)
* [Download](https://eprint.iacr.org/2023/774.pdf)
### Abstract
Chameleon hash (CH) is a trapdoor hash function. Generally it is hard to find collisions, but with the help of trapdoor, finding collisions becomes easy. CH plays an important role in converting a conventional blockchain to a redactable one. However, most of the existing CH schemes are too weak to support redactable blockchain. The currently known CH schemes serving for redactable blockchain have the best security of so-called “full collision resistance (f-CR)”, but they are built either on random oracle model or rely on heavy tools like the simulation-sound extractable non-interactive zero-knowledge (SSE-NIZK) proof system. Moreover, up to now there is no CH scheme with post-quantum f-CR security in the standard model. Therefore, no CH can support redactable blockchain in a post-quantum way without relying on random oracles.
In this paper, we introduce a variant of CH, namely tagged chameleon hash (tCH). Tagged chameleon hash takes a tag into hash evaluations and collision finding algorithms. We define two security notions for tCH, collision resistance (CR) and full collision resistance (f-CR), and prove the equivalence between CR and f-CR when tCH works in the one-time tag mode. We propose a tCH scheme from lattice without using any NIZK proof, and prove that its collision resistance is (almost) tightly reduced to the Short Integer Solution (SIS) assumption in the standard model. We also show how to apply tCH to a blockchain in one-time tag mode so that the blockchain can be compiled to a redactable one. Our tCH scheme provides the first post-quantum solution for redactable blockchains, without resorting to random oracles or NIZK proofs. Besides, we also construct a more efficient tCH scheme with CR tightly reduced to SIS in the random oracle model, which may be of independent interest.
## 2023/775
* Title: Exact Security Analysis of ASCON
* Authors: Bishwajit Chakraborty, Chandranan Dhar, Mridul Nandi
* [Permalink](https://eprint.iacr.org/2023/775)
* [Download](https://eprint.iacr.org/2023/775.pdf)
### Abstract
The Ascon cipher suite, offering both authenticated encryption with associated data (AEAD) and hashing functionality, has recently emerged as the winner of the NIST Lightweight Cryptography (LwC) standardization process. The AEAD schemes within Ascon, namely Ascon-128 and Ascon-128a, have also been previously selected as the preferred lightweight authenticated encryption solutions in the CAESAR competition. In this paper, we present a tight and comprehensive security analysis of the Ascon AEAD schemes within the random permutation model. Existing integrity analyses of Ascon (and any Duplex AEAD scheme in general) commonly include the term $DT/2^c$, where $D$ and $T$ represent data and time complexities respectively, and $c$ denotes the capacity of the underlying sponge. In this paper, we demonstrate that Ascon achieves AE security when $T$ is bounded by $\min\{2^{\kappa}, 2^c\}$ (where $\kappa$ is the key size), and $DT$ is limited to $2^b$ (with $b$ being the size of the underlying permutation, which is 320 for Ascon). Our findings indicate that in accordance with NIST requirements, Ascon allows for a tag size as low as 64 bits while enabling a higher rate of 192 bits, surpassing the recommended rate.
## 2023/776
* Title: Quantum Attacks on Type-1 Generalized Feistel Schemes
* Authors: Hong-Wei Sun, Bin-Bin Cai, Su-Juan Qin, Qiao-Yan Wen, Fei Gao
* [Permalink](https://eprint.iacr.org/2023/776)
* [Download](https://eprint.iacr.org/2023/776.pdf)
### Abstract
Generalized Feistel schemes (GFSs) are extremely important and extensively researched cryptographic schemes. In this paper, we investigate the security of Type-1 GFS in quantum circumstances. On the one hand, in the qCCA setting, we give a new quantum polynomial time distinguisher on (d^2 -1)-round Type-1 GFS with branches d >3, which extends the previous results by d-2 rounds. This leads to a more efficient analysis of type-1 GFS, that is, the complexity of some previous key-recovery attacks is reduced by a factor of 2^(((d-2)k)/2), where k is the key length of the internal round function. On the other hand, for CAST-256, which is a certain block cipher based on Type-1 GFS, we give a 17-round quantum distinguisher in the qCPA setting. As a result, we construct an r(r > 17) round quantum key-recovery attack with complexity O(2^(37(r-17))/2 ).
## 2023/777
* Title: Too Many Hints - When LLL Breaks LWE
* Authors: Alexander May, Julian Nowakowski
* [Permalink](https://eprint.iacr.org/2023/777)
* [Download](https://eprint.iacr.org/2023/777.pdf)
### Abstract
All modern lattice-based schemes build on variants of the LWE problem. Information leakage of the LWE secret $\mathbf s \in \mathbb{Z}_q^n$ is usually modeled via so-called hints, i.e., inner products of $\mathbf s$ with some (random, but known) vector.
At Crypto`20, Dachman-Soled, Ducas, Gong and Rossi (DDGR) defined among other so-called perfect hints and modular hints. The trailblazing DDGR framework allows to integrate and combine hints successively into lattices, and estimates the resulting LWE security loss.
We introduce a new methodology to integrate and combine an arbitrary number of perfect and modular in a single stroke. As opposed to DDGR, our methodology is significantly more efficient in constructing lattice bases, and thus easily allows for a large number of hints up to cryptographic dimensions, a regime that is impractical in DDGR. The efficiency of our method defines a large LWE parameter regime, in which we can fully carry out attacks faster than DDGR can solely estimate them. A key component of our new method is dimension reduction of $\mathbf s$, which significantly reduces LWE security.
The benefits of our approach allow us to practically determine which number of hints is sufficient to efficiently break LWE-based lattice schemes in practice. For mod-$q$ hints, i.e., modular hints defined over $\mathbb{Z}_q$, we reconstruct Kyber-512 secret keys via LLL reduction (only!) with an amount of $449$ hints. For Falcon-512, NTRU-HRSS-701, Kyber-768 and Dilithium-1024 we need $452$, $622$, $702$ and $876$ modular hints, respectively.
Our results for perfect hints significantly improve over these numbers, requiring for LWE dimension $n$ roughly $n/2$ perfect hints. Namely, we reconstruct via LLL reduction Kyber-512 keys with merely $234$ perfect hints. For secret keys of Falcon-512, NTRU-HRSS-701, Kyber-768 and Dilithium-1024 we require $233$, $332$, $390$ and $463$ perfect hints, respectively. We find such a small amount of perfect hints quite remarkable. If we resort to stronger lattice reduction techniques like BKZ, we need even fewer hints.
For mod-$q$ hints our method is extremely efficient, taking total time for constructing our lattice bases and secret key recovery via LLL of around 20 mins for dimension 512, 40 mins for dimensions 701 and 768, and less than 10 hours for dimension 1024. For perfect hints we require around 3 hours (dim 512), 11 hours (dim 701), 1 day (dim 768), and one week (dim 1024).
Our results demonstrate that especially perfect hints are powerful in practice, and stress the necessity to properly protect lattice schemes against leakage.
## 2023/778
* Title: Bounded Verification for Finite-Field-Blasting (In a Compiler for Zero Knowledge Proofs)
* Authors: Alex Ozdemir, Riad S. Wahby, Fraser Brown, Clark Barrett
* [Permalink](https://eprint.iacr.org/2023/778)
* [Download](https://eprint.iacr.org/2023/778.pdf)
### Abstract
Zero Knowledge Proofs (ZKPs) are cryptographic protocols
by which a prover convinces a verifier of the truth of a statement with-
out revealing any other information. Typically, statements are expressed
in a high-level language and then compiled to a low-level representation
on which the ZKP operates. Thus, a bug in a ZKP compiler can com-
promise the statement that the ZK proof is supposed to establish. This
paper takes a step towards ZKP compiler correctness by partially veri-
fying a field-blasting compiler pass, a pass that translates Boolean and
bit-vector logic into equivalent operations in a finite field. First, we define
correctness for field-blasters and ZKP compilers more generally. Next, we
describe the specific field-blaster using a set of encoding rules and de-
fine verification conditions for individual rules. Finally, we connect the
rules and the correctness definition by showing that if our verification
conditions hold, the field-blaster is correct. We have implemented our
approach in the CirC ZKP compiler and have proved bounded versions
of the corresponding verification conditions. We show that our partially
verified field-blaster does not hurt the performance of the compiler or its
output; we also report on four bugs uncovered during verification.
## 2023/779
* Title: Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the Cryptanalysis of pSIDH
* Authors: Mingjie Chen, Muhammad Imran, Gábor Ivanyos, Péter Kutas, Antonin Leroux, Christophe Petit
* [Permalink](https://eprint.iacr.org/2023/779)
* [Download](https://eprint.iacr.org/2023/779.pdf)
### Abstract
The Isogeny to Endomorphism Ring Problem (IsERP) asks to compute the endomorphism ring of the codomain of an isogeny between supersingular curves in characteristic $p$ given only a representation for this isogeny, i.e. some data and an algorithm to evaluate this isogeny on any torsion point. This problem plays a central role in isogeny-based cryptography; it underlies the security of
pSIDH protocol (ASIACRYPT 2022) and it is at the heart of the recent attacks that broke the SIDH key exchange. Prior to this work, no efficient algorithm was known to solve IsERP for a generic isogeny degree, the hardest case seemingly when the degree is prime.
In this paper, we introduce a new quantum polynomial-time algorithm to solve IsERP for isogenies whose degrees are odd and have $O(\log\log p)$ many prime factors. As main technical tools, our algorithm uses a quantum algorithm for computing hidden Borel subgroups, a group action on supersingular isogenies from EUROCRYPT 2021, various algorithms for the Deuring correspondence and a new algorithm to lift arbitrary quaternion order elements modulo an odd integer $N$ with $O(\log\log p)$ many prime factors to powersmooth elements.
As a main consequence for cryptography, we obtain a quantum polynomial-time key recovery attack on pSIDH. The technical tools we use may also be of independent interest.
## 2023/780
* Title: An Anonymous Multi-receiver Certificateless Hybrid Signcryption (AMCLHS) using mKEM-DEM for Broadcast Communication
* Authors: Alia Umrani, Apurva K Vangujar, Paolo Palmieri
* [Permalink](https://eprint.iacr.org/2023/780)
* [Download](https://eprint.iacr.org/2023/780.pdf)
### Abstract
Confidentiality, authentication, and anonymity are the fundamental security requirements in broadcast communication that can be achieved by Digital Signature (DS), encryption, and pseudo-anonymous identity techniques. Signcryption offer both DS and encryption in a single logical step with high efficiency. Similarly, anonymous multireceiver signcryption ensure receiver privacy by generating identical ciphertext for multiple receivers while keeping their identities private. While signcryption is a significant improvement over “sign then encrypt”, it still incurs higher computational and communication cost and does not provide the required level of security.
In this paper, we propose a multiple-recipient Key Encapsulation Mechanism (mKEM) - Data Encapsulation Mechanism (DEM) based Anonymous Multireceiver Certificateless Hybrid Signcryption (AMCLHS). The AMCLHS uses a combination of symmetric key and asymmetric key cryptography to signcrypt an arbitrary length message in broadcast communication and has two unique settings as follows:
Pseudo-Identity PID Settings: We introduce a new algorithmic step in AMCLHS construction where each user (sender and receiver) is assigned a PID to enable the sender to signcrypt identical messages for multiple receivers while keeping the identities of other receivers anonymous.
The receiver anonymity is achieved by choosing random Real-Identity (ID_R) to generate PID of the users in key generation algorithm of AMCLHS scheme. Our approach relies on the Elliptic Curve Discrete Logarithm (ECDL) hardness assumptions, the hash function, and verification-based secret key of the Register Authority (RA), using time Delta T.
mKEM-DEM Settings: We introduce the first construction that achieves optimal ciphertext from the Diffie-Hellman (DH) assumption using mKEM-DEM for Signcryption. Our scheme uses mKEM to generate a symmetric key for multiple-receivers and DEM to signcrypt message using the previously generated symmetric key and the sender's private key. mKEM for key setup and Signcryption for confidentiality and forward security, and DEM for key generation and unsigncryption for indistinguishability under Indistinguishability against Chosen Ciphertext Attack (IND-CCA2).
Our scheme relies on DH and Bilinear Pairing (BP) assumption and uses a single key for all messages, which minimizes ciphertext length and ultimately reduces complexity overhead.
The scheme operates in a multireceiver certificateless environment, preventing the key escrow problem, and demonstrates cryptographic notions for Indistinguishability under Chosen-Ciphertext Attack (IND-CCA2) and Existential Unforgeability against Chosen Message Attack (EUF-CMA) for Type-I and Type-II adversaries under q-Decisional Bilinear Diffie-Hellman Inversion (q-DBDHI) and ECDL hard assumptions. We compare the proposed scheme with existing multireceiver hybrid signcryption schemes in terms of computation cost, communication cost, and security requirements. We show that, compared to existing multireceiver schemes which has overall cost of O(n^2), our scheme is computationally more efficient and has optimal communication cost, with signcryption cost linear O(n) to the number of designated receivers while the unsigncryption cost remains constant O(1). Our scheme achieves confidentiality, authentication, anonymity, and simultaneously achieves unlinkability, non-repudiation, and forward security.
## 2023/781
* Title: $\mathsf{Skye}$: A Fast KDF based on Expanding PRF and its Application to Signal
* Authors: Amit Singh Bhati, Antonin Dufka, Elena Andreeva, Arnab Roy, Bart Preneel
* [Permalink](https://eprint.iacr.org/2023/781)
* [Download](https://eprint.iacr.org/2023/781.pdf)
### Abstract
A Key Derivation Function KDF generates a uniform and highly random key-stream from weakly random key material. KDFs are broadly used in various security protocols such as digital signatures and key exchange protocols. HKDF is the most deployed KDF in practice. It is based on the $\textit{extract-then-expand}$ paradigm and is presently used, among others, in the Signal Protocol for end-to-end encrypted messaging.
HKDF was proposed as a generic KDF for general input sources and thus is not optimized for source-specific use cases such as key derivation from Diffie-Hellman (DH) sources (i.e. DH shared secrets as key material). Furthermore, the sequential HKDF design is unnecessarily slower on some general-purpose platforms that benefit from parallelization.
In this work, we propose a novel, efficient and secure KDF called $\mathsf{Skye}$. $\mathsf{Skye}$ follows the $\textit{extract-then-expand}$ paradigm and consists of two algorithms: efficient deterministic $\textit{randomness extractor}$ and $\textit{expansion}$ functions. Instantiating our extractor for dedicated source-specific (e.g. DH sources) inputs allows us to achieve a significant efficiency speed-up over HKDF at the same security level. We provide concrete security analysis of $\mathsf{Skye}$ and both its algorithms in the standard model.
We provide a software performance comparison of $\mathsf{Skye}$ with the AES-based expanding PRF $\mathsf{ButterKnife}$ and HKDF with SHA-256 (as used in Signal). Our results show that in isolation $\mathsf{Skye}$ performs from 4x to 47x faster than HKDF, depending on the platform instruction support. We further demonstrate that with such a performance gain, when $\mathsf{Skye}$ is integrated within the current Signal implementation, we can achieve significant overall improvements ranging from $38\%$ to $64\%$ relative speedup in unidirectional messaging. Even in bidirectional messaging, that includes DH computation with dominating computational cost, $\mathsf{Skye}$ still contributes to $12-36\%$ relative speedup when just 10 messages are sent and received at once.
## 2023/782
* Title: Coefficient Grouping for Complex Affine Layers
* Authors: Fukang Liu, Lorenzo Grassi, Clémence Bouvier, Willi Meier, Takanori Isobe
* [Permalink](https://eprint.iacr.org/2023/782)
* [Download](https://eprint.iacr.org/2023/782.pdf)
### Abstract
Designing symmetric-key primitives for applications in Fully Homomorphic Encryption (FHE) has become important to address the issue of the ciphertext expansion. In such a context, cryptographic primitives with a low-AND-depth decryption circuit are desired. Consequently, quadratic nonlinear functions are commonly used in these primitives, including the well-known $\chi$ function over $\mathbb{F}_2^n$ and the power map over a large finite field $\mathbb{F}_{p^n}$. In this work, we study the growth of the algebraic degree for an SPN cipher over $\mathbb{F}_{2^n}^{m}$, whose S-box is defined as the combination of a power map $x\mapsto x^{2^d+1}$ and an $\mathbb{F}_2$-linearized affine polynomial $x\mapsto c_0+\sum_{i=1}^{w}c_ix^{2^{h_i}}$ where $c_1,\ldots,c_w\neq0$. Specifically, motivated by the fact that the original coefficient grouping technique published at EUROCRYPT 2023 becomes less efficient for $w>1$, we develop a variant technique that can efficiently work for arbitrary $w$. With this new technique to study the upper bound of the algebraic degree, we answer the following questions from a theoretic perspective:
1. can the algebraic degree increase exponentially when $w=1$?
2. what is the influence of $w$, $d$ and $(h_1,\ldots,h_w)$ on the growth of the algebraic degree?
Based on this, we show (i) how to efficiently find $(h_1,\ldots,h_w)$ to achieve the exponential growth of the algebraic degree and (ii) how to efficiently compute the upper bound of the algebraic degree for arbitrary $(h_1,\ldots,h_w)$. Therefore, we expect that these results can further advance the understanding of the design and analysis of such primitives.
## 2023/783
* Title: Breaking the power-of-two barrier: noise estimation for BGV in NTT-friendly rings
* Authors: Andrea Di Giusto, Chiara Marcolla
* [Permalink](https://eprint.iacr.org/2023/783)
* [Download](https://eprint.iacr.org/2023/783.pdf)
### Abstract
The Brakerski-Gentry-Vaikuntanathan (BGV) scheme is a Fully Homomorphic Encryption (FHE) cryptosystem based on the Ring Learning With Error (RLWE) problem.
Ciphertexts in this scheme contain an error term that grows with operations and causes decryption failure when it surpasses a certain threshold.
For this reason, the parameters of BGV need to be estimated carefully, with a trade-off between security and error margin.
The ciphertext space of BGV is the ring $\mathcal R_q=\mathbb Z_q[x]/(\Phi_m(x))$, where usually the degree $n$ of the cyclotomic polynomial $\Phi_m(x)$ is chosen as a power of two for efficiency reasons. However, the jump between two consecutive powers-of-two polynomials can sometimes also cause a jump of the security, resulting in parameters that are much bigger than what is needed.
In this work, we explore the non-power-of-two instantiations of BGV.
Although our theoretical research encompasses results applicable to any cyclotomic ring, our main investigation is focused on the case of $m=2^s 3^t$, i.e., cyclotomic polynomials with degree $n=2^s 3^{t-1}$.
We provide a thorough analysis of the noise growth in this new setting using the canonical norm and compare our results with the power-of-two case considering practical aspects like NTT algorithms.
We find that in many instances, the parameter estimation process yields better results for the non-power-of-two setting.
## 2023/784
* Title: History-Free Sequential Aggregate Signatures from Generic Trapdoor Functions
* Authors: Alessio Meneghetti, Edoardo Signorini
* [Permalink](https://eprint.iacr.org/2023/784)
* [Download](https://eprint.iacr.org/2023/784.pdf)
### Abstract
A sequential aggregate signature (SAS) scheme allows multiple users to sequentially combine their respective signatures in order to reduce communication costs. Historically, early proposals required the use of trapdoor permutation (e.g., RSA).
In recent years, a number of attempts have been made to extend SAS schemes to post-quantum assumptions. Many post-quantum signatures have been proposed in the hash-and-sign paradigm, which requires the use of trapdoor functions and appears to be an ideal candidate for sequential aggregation attempts. However, the hardness in achieving post-quantum one-way permutations makes it difficult to obtain similarly general constructions. Direct attempts at generalizing permutation-based schemes have been proposed, but they either lack formal security or require additional properties on the trapdoor function, which are typically not available for multivariate or code-based functions.
In this paper, we propose a history-free sequential aggregate signature based on generic trapdoor functions, generalizing existing techniques. We prove the security of our scheme in the random oracle model by adopting the probabilistic hash-and-sign with retry paradigm, and we instantiate our construction with three post-quantum schemes, comparing their compression capabilities. Finally, we discuss how direct extensions of permutation-based SAS schemes are not possible without additional properties, showing the insecurity of two existing multivariate schemes when instantiated with Unbalanced Oil and Vinegar.
## 2023/785
* Title: Generation of two ''independent'' points on an elliptic curve of $j$-invariant $\neq 0, 1728$
* Authors: Dmitrii Koshelev
* [Permalink](https://eprint.iacr.org/2023/785)
* [Download](https://eprint.iacr.org/2023/785.pdf)
### Abstract
This article is dedicated to a new generation method of two ``independent'' $\mathbb{F}_{\!q}$-points $P_0$, $P_1$ on almost any ordinary elliptic curve $E$ over a finite field $\mathbb{F}_{\!q}$ of large characteristic. In particular, the method is relevant for all standardized and real-world elliptic curves of $j$-invariants different from $0$, $1728$. The points $P_0$, $P_1$ are characterized by the fact that nobody (even a generator) knows the discrete logarithm $\log_{P_0}(P_1)$ in the group $E(\mathbb{F}_{\!q})$. Moreover, only one square root extraction in $\mathbb{F}_{\!q}$ (instead of two ones) is required in comparison with all previous generation methods.
## 2023/786
* Title: Blockchain Transaction Censorship: (In)secure and (In)efficient?
* Authors: Zhipeng Wang, Xihan Xiong, William J. Knottenbelt
* [Permalink](https://eprint.iacr.org/2023/786)
* [Download](https://eprint.iacr.org/2023/786.pdf)
### Abstract
The ecosystem around blockchain and Decentralized Finance (DeFi) is seeing more and more interest from centralized regulators. For instance, recently, the US government placed sanctions on the largest DeFi mixer, Tornado.Cash (TC). To our knowledge, this is the first time that centralized regulators sanction a decentralized and open-source blockchain application. It has led various blockchain participants, e.g., miners/validators and DeFi platforms, to censor TC-related transactions. The blockchain community has extensively discussed that censoring transactions could affect users’ privacy.
In this work, we analyze the efficiency and possible security implications of censorship on the different steps during the life cycle of a blockchain transaction, i.e., generation, propagation, and validation. We reveal that fine-grained censorship will reduce the security of block validators and centralized transaction propagation services, and can potentially cause Denial of Service (DoS) attacks. We also find that DeFi platforms adopt centralized third-party services to censor user addresses at the frontend level, which blockchain users could easily bypass. Moreover, we present a tainting attack whereby an adversary can prevent users from interacting normally with DeFi platforms by sending TC-related transactions.
## 2023/787
* Title: Private Proof-of-Stake Blockchains using Differentially-private Stake Distortion
* Authors: Chenghong Wang, David Pujo, Kartik Nayak, Ashwin Machanavajjhala
* [Permalink](https://eprint.iacr.org/2023/787)
* [Download](https://eprint.iacr.org/2023/787.pdf)
### Abstract
Safety, liveness, and privacy are three critical properties for any private proof-of-stake (PoS) blockchain. However, prior work (SP'21) has shown that to obtain safety and liveness, a PoS blockchain must in theory forgo privacy. Specifically, to ensure safety and liveness, PoS blockchains elect parties based on stake proportion, potentially exposing a party's stake even with private transaction processing. In this work, we make two key contributions. First, we present the first stake inference attack applicable to both deterministic and randomized PoS with exponentially less running time in comparison with SOTA designs. Second, we use differentially private stake distortion to achieve privacy in PoS blockchains and design two stake distortion mechanisms that any PoS protocol can use. We further evaluate our proposed methods using Ethereum 2.0, a widely-recognized PoS blockchain in operation. Results demonstrate effective stake inference risk mitigation, reasonable privacy, and preservation of essential safety and liveness properties.
## 2023/788
* Title: A flexible Snark via the monomial basis
* Authors: Steve Thakur
* [Permalink](https://eprint.iacr.org/2023/788)
* [Download](https://eprint.iacr.org/2023/788.pdf)
### Abstract
We describe a pairing-based SNARK with a universal updateable CRS that can be instantiated with any pairing-friendly curve endowed with a sufficiently large prime scalar field. We use the monomial basis, thus sidestepping the need for large smooth order subgroups in the scalar field. In particular, the scheme can be instantiated with outer curves to widely used curves such as Ed25519, secp256k1 and BN254. This allows us to largely circumvent the overhead of non-native field arithmetic for succinct proofs of statements in these base fields. These include proofs of valid signatures in Ed25519 and secp256k1 and one layer recursion with BN254.
The proof size is constant \( (10\; \mathbb{G}_1\), \(20\;\mathbb{F}_p)\), as is the verification runtime, which is dominated by a single pairing check (i.e. two pairings). The Prover time is dominated by the \(10\) multi-scalar multiplications in \(\mathbb{G}_1\) - with a combined MSM length of $22\cdot |\mathrm{Circuit}|$ - and, to a lesser extent, the computation of a single sum of polynomial products over the scalar field.
The scheme supports succinct lookup arguments for subsets as well as subsequences. Our construction relies on homomorphic table commitments, which makes them amenable to vector lookups. The Prover algorithm runs in runtime $O(M\cdot \log(M))$, where $M = \max \{|\text{Circuit}| , \;|\text{Table}|\}.$
When the scalar field has low $2$-adicity - as is inevitably the case with any outer curve to Ed25519, secp256k1 or BN254 - we use the Schonhage-Strassen algorithm or the multimodular FFT algorithm to compute the sum of polynomial products that occurs in one of the steps of the proof generation. Despite the small (but discernible) slowdown compared to polynomial products in FFT-friendly fields, we empirically found that the MSMs dominate the proof generation time. To that end, we have included some benchmarks for polynomial products in FFT-unfriendly fields.
Furthermore, the scheme supports custom gates, albeit at the cost of a larger proof size. As an application of the techniques in this paper, we describe a protocol that supports multiple \( \mathbf{univariate}\) custom gates $\mathcal{G}_i$ of high degree that are sparsely distributed, in the sense that \[ \sum_{i} \deg(\mathcal{G}_i)\cdot \#(\mathcal{G}_i\;\text{gates}) \; = \; O(|\text{Circuit}|). \] This comes at the cost of three additional $\mathbb{G}_1$ elements and does not blow up the proof generation time, i.e. it does not entail MSMs or FFTs of length larger than the circuit size.
At the moment, Panther Protocol's Rust implementation in a 576-bit pairing-friendly outer curve to Ed25519 has a (not yet optimized) Prover time of 45 seconds for a million gate circuit on a 64 vCPU AWS machine.
0 new messages