IACR News
Updates on the COVID-19 situation are on the
Announcement channel.
Here you can see all recent updates to the IACR webpage. These updates are also available:
24 September 2023
Alexandra Henzinger, Emma Dauterman, Henry Corrigan-Gibbs, Nickolai Zeldovich
Tiptoe is a private web search engine that allows clients to search over hundreds of millions of documents, while revealing no information about their search query to the search engine’s servers. Tiptoe’s privacy guarantee is based on cryptography alone; it does not require hardware enclaves or non-colluding servers. Tiptoe uses semantic embeddings to reduce the problem of private full-text search to private nearest-neighbor search. Then, Tiptoe implements private nearest-neighbor search with a new, high-throughput protocol based on linearly homomorphic encryption. Running on a 45-server cluster, Tiptoe can privately search over 360 million web pages with 145 core-seconds of server compute, 56.9 MiB of client-server communication (74% of which occurs before the client enters its search query), and 2.7 seconds of end-to-end latency. Tiptoe’s search works best on conceptual queries (“knee pain”) and less well on exact string matches (“123 Main Street, New York”). On the MS MARCO search-quality benchmark, Tiptoe ranks the best-matching result in position 7.7 on average. This is worse than a state-of-the-art, non-private neural search algorithm (average rank: 2.3), but is close to the classical tf-idf algorithm (average rank: 6.7). Finally, Tiptoe is extensible: it also supports private text-to-image search and, with minor modifications, it can search over audio, code, and more.
YongRyeol Choi, MinGi Kim, YoungBeom Kim, JinGyo Song, JaeHwan Jin, HeeSeok Kim, Seong Chung Seo
As the global migration to post-quantum cryptography (PQC) continues to progress actively, in Korea, the Post-Quantum Cryptography Research Center has been established to acquire PQC technology, leading the KpqC Competition. In February 2022, the KpqC Competition issued a call for proposals for PQC algorithms. By November 2022, a total of 16 candidates were selected for the first round (7 KEMs and 9 DSAs). Currently, round 1 submissions are being evaluated with respect to security, efficiency, and scalability in various environments. At the current stage, evaluating the software through an analysis to improve the software quality of the first-round submissions is judged appropriately. In this paper, we present analysis results regarding performance and implementation security on based dependency-free approach of external libraries. Namely, we configure extensive tests for an analysis with no dependencies by replacing external libraries that can complicate the build process with hard coding. From the performance perspective, we provide analysis results of performance profiling, execution time, and memory usage for each of KpqC candidates. From the implementation security perspective, we examine bugs and errors in the actual implementations using Valgrind software, metamorphic testing methodology that can include wide test coverage and constant-time implementation against the timing attack. As a result, we found implementation bugs and errors in two submissions, metamorphic testing errors in one submission, and non-constant-time implementation in one submission. Until the KpqC standard algorithm is announced, we argue that continuous integration of extensive tests will lead to higher-level software quality of KpqC candidates.
Henri Gilbert, Rachelle Heim Boissier, Jérémy Jean, Jean-René Reinhard
Elisabeth-4 is a stream cipher tailored for usage in hybrid homomorphic encryption applications that has been introduced by Cosseron et al. at ASIACRYPT 2022. In this paper, we present several variants of a key-recovery attack on the full Elisabeth-4 that break the 128-bit security claim of that cipher. Our most optimized attack is a chosen-IV attack with a time complexity of $2^{88}$ elementary operations, a memory complexity of $2^{54}$ bits and a data complexity of $2^{41}$ bits.
Our attack applies the linearization technique to a nonlinear system of equations relating some keystream bits to the key bits and exploits specificities of the cipher to solve the resulting linear system efficiently. First, due to the structure of the cipher, the system to solve happens to be very sparse, which enables to rely on sparse linear algebra and most notably on the Block Wiedemann algorithm. Secondly, the algebraic properties of the two nonlinear ingredients of the filtering function cause rank defects which can be leveraged to solve the linearized system more efficiently with a decreased data and time complexity.
We have implemented our attack on a toy version of Elisabeth-4 to verify its correctness. It uses the efficient implementation of the Block Wiedemann algorithm of CADO-NFS for the sparse linear algebra.
Our attack applies the linearization technique to a nonlinear system of equations relating some keystream bits to the key bits and exploits specificities of the cipher to solve the resulting linear system efficiently. First, due to the structure of the cipher, the system to solve happens to be very sparse, which enables to rely on sparse linear algebra and most notably on the Block Wiedemann algorithm. Secondly, the algebraic properties of the two nonlinear ingredients of the filtering function cause rank defects which can be leveraged to solve the linearized system more efficiently with a decreased data and time complexity.
We have implemented our attack on a toy version of Elisabeth-4 to verify its correctness. It uses the efficient implementation of the Block Wiedemann algorithm of CADO-NFS for the sparse linear algebra.
Sohto Chiku, Keitaro Hashimoto, Keisuke Hara, Junji Shikata
Identity-based matchmaking encryption (IB-ME), proposed by Ateniese et al. at Crypto 2019, allows users to communicate privately in an anonymous and authenticated manner. In this work, we revisit the security definitions and construction of IB-ME. First, we re-formalize the existing security notions for IB-ME. We reorganize privacy and authenticity notions into respective three and four definitions, which allows us to compare IB-ME schemes accurately. Second, we propose a highly efficient and strongly secure IB-ME scheme from the bilinear Diffie-Hellman assumption in the random oracle model. This scheme is based on the IB-ME scheme proposed by Ateniese et al., but we introduce several techniques to improve its security and efficiency. Third, we propose a new generic construction of IB-ME from anonymous identity-based encryption and identity-based signature. This is the first generic construction that does not rely on hierarchical identity-based encryption. Through this construction, we obtain various IB-ME schemes from both classical and post-quantum assumptions. For example, we obtain a more efficient scheme from the symmetric external Diffie-Hellman assumption in the standard model, and a practical scheme from lattices in the quantum random oracle model whose secret keys and ciphertexts are less than 10 Kilobytes. Moreover, our generic construction produces the first pairing-free IB-ME scheme in the standard model and the first tightly secure lattice-based IB-ME scheme in the quantum random oracle model.
Ian McQuoid, Jiayu Xu
Password-authenticated key exchange (PAKE) is a class of protocols enabling two parties to convert a shared (possibly low-entropy) password into a high-entropy joint session key. Strong asymmetric PAKE (saPAKE), an extension that models the client-server setting where servers may store a client's password for repeated authentication, was the subject of standardization efforts by the IETF in 2019-20. In this work, we present the most computationally efficient saPAKE protocol so far: a compiler from PAKE to saPAKE which costs only 2 messages and 7 group exponentiations in total (3 for client and 4 for server) when instantiated with suitable underlying PAKE protocols. In addition to being efficient, our saPAKE protocol is conceptually simple and achieves the strongest notion of universally composable (UC) security.
In addition to classical assumptions and classical PAKE, we may instantiate our PAKE-to-saPAKE compiler with cryptographic group actions, such as the isogeny-based CSIDH, and post-quantum PAKE. This yields the first saPAKE protocol from post-quantum assumptions as all previous constructions rely on cryptographic assumptions weak to Shor's algorithm.
In addition to classical assumptions and classical PAKE, we may instantiate our PAKE-to-saPAKE compiler with cryptographic group actions, such as the isogeny-based CSIDH, and post-quantum PAKE. This yields the first saPAKE protocol from post-quantum assumptions as all previous constructions rely on cryptographic assumptions weak to Shor's algorithm.
Wouter Castryck, Frederik Vercauteren
The recent devastating attacks on SIDH rely on the fact that the protocol reveals the images $\varphi(P)$ and $\varphi(Q)$ of the secret isogeny $\varphi : E_0 \rightarrow E$ on a basis $\{P, Q\}$ of the $N$-torsion subgroup $E_0[N]$ where $N^2 > \deg(\varphi)$. To thwart this attack, two recent proposals, M-SIDH and FESTA, proceed by only revealing the images upto unknown scalars $\lambda_1, \lambda_2 \in \mathbb{Z}_N^\times$, i.e., only $\lambda_1 \varphi(P)$ and $\lambda_2 \varphi(Q)$ are revealed, where $\lambda_1 = \lambda_2$ for M-SIDH and $\lambda_1 = \lambda_2^{-1}$ for FESTA. Similar information is leaked in CSIDH since $\varphi$ maps the eigenspaces of Frobenius on $E_0$ to the corresponding eigenspaces on $E$.
In this paper, we introduce a new polynomial time attack that generalizes the well known "lollipop" attack and analyze how it applies to M-SIDH, FESTA and CSIDH. We show that M-SIDH can be broken in polynomial time whenever $E_0$ or $E$ is $\mathbb{F}_p$-rational, even when the endomorphism rings of $E_0$ and $E$ are unknown. This can be generalized to the case where the starting (or end) curve is not $\mathbb{F}_p$-rational, but is connected to its Frobenius conjugate by an isogeny of small degree.
For FESTA, where the curve $E_0$ is already $\mathbb{F}_p$-rational, we obtain a polynomial time attack under the added requirement that at least one of the basis points $P, Q$ spans an eigenspace of Frobenius, of an endomorphism of low degree, or of a composition of both. We note that the current implementation of FESTA does not choose such a basis. Since it is always possible to construct an endomorphism, typically of large degree, with either $P, Q$ an eigenvector, we conclude that FESTA with overstretched parameters is insecure.
Although the information leaked in CSIDH is very similar to FESTA, we show that our attack does not reveal any new information about the secret isogeny, i.e., we only learn that it is $\mathbb{F}_p$-rational, which is a priori knowledge.
Finally, we analyze if and how it would be possible to backdoor M-SIDH and FESTA by choosing system parameters that look inconspicuous, but in fact reduce to the special cases above via a secret isogeny chosen by the adversary.
For FESTA, where the curve $E_0$ is already $\mathbb{F}_p$-rational, we obtain a polynomial time attack under the added requirement that at least one of the basis points $P, Q$ spans an eigenspace of Frobenius, of an endomorphism of low degree, or of a composition of both. We note that the current implementation of FESTA does not choose such a basis. Since it is always possible to construct an endomorphism, typically of large degree, with either $P, Q$ an eigenvector, we conclude that FESTA with overstretched parameters is insecure.
Although the information leaked in CSIDH is very similar to FESTA, we show that our attack does not reveal any new information about the secret isogeny, i.e., we only learn that it is $\mathbb{F}_p$-rational, which is a priori knowledge.
Finally, we analyze if and how it would be possible to backdoor M-SIDH and FESTA by choosing system parameters that look inconspicuous, but in fact reduce to the special cases above via a secret isogeny chosen by the adversary.
Jean Paul Degabriele, Vukašin Karadžić
A Rugged Pseudorandom Permutation (RPRP) is a variable-input-length tweakable cipher satisfying a security notion that is intermediate between tweakable PRP and tweakable SPRP. It was introduced at CRYPTO 2022 by Degabriele and Karadžić, who additionally showed how to generically convert such a primitive into nonce-based and nonce-hiding AEAD schemes satisfying either misuse-resistance or release-of-unverified-plaintext security as well as Nonce-Set AEAD which has applications in protocols like QUIC and DTLS. Their work shows that RPRPs are powerful and versatile cryptographic primitives. However, the RPRP security notion itself can seem rather contrived, and the motivation behind it is not immediately clear. Moreover, they only provided a single RPRP construction, called UIV, which puts into question the generality of their modular approach and whether other instantiations are even possible. In this work, we address this question positively by presenting new RPRP constructions, thereby validating their modular approach and providing further justification in support of the RPRP security definition. Furthermore, we present a more refined view of their results by showing that strictly weaker RPRP variants, which we introduce, suffice for many of their transformations. From a theoretical perspective, our results show that the well-known three-round Feistel structure achieves stronger security as a permutation than a mere pseudorandom permutation---as was established in the seminal result by Luby and Rackoff. We conclude on a more practical note by showing how to extend the left domain of one RPRP construction for applications that require larger values in order to meet the desired level of security.
Yaobin Shen, François-Xavier Standaert, Lei Wang
At CRYPTO'18, Datta et al. proposed nPolyMAC and proved the security up to 2^{2n/3} authentication queries and 2^{n} verification queries. At EUROCRYPT'19, Dutta et al. proposed CWC+ and showed the security up to 2^{2n/3} queries. At FSE'19, Datta et al. proposed PolyMAC and its key-reduced variant 2k-PolyMAC, and showed the security up to 2^{2n/3} queries. This security bound was then improved by Kim et al. (EUROCRYPT'20) and Datta et al (FSE'23) respectively to 2^{3n/4} and in the multi-user setting. At FSE'20, Chakraborti et al. proposed PDM*MAC and 1k-PDM*MAC and showed the security up to 2^{2n/3} queries. Recently, Chen et al. proposed nEHtM_p^+ and showed the security up to 2^{2n/3} queries. In this paper, we show forgery attacks on nPolyMAC, CWC+, PolyMAC, 2k-PolyMAC, PDM*MAC, 1k-PDM*MAC and nEHtM_p^+. Our attacks exploit some vulnerability in the underlying polynomial hash function Poly, and (i) require only one authentication query and one verification query; (ii) are nonce-respecting; (iii) succeed with probability 1. Thus, our attacks disprove the provable high security claims of these schemes. We then revisit their security analyses and identify what went wrong. Finally, we propose two solutions that can restore the beyond-birthday-bound security.
Zhengjun Cao, Lihua Liu
We show that the key agreement scheme [J. Syst. Archit., 131:102698, 2022] fails to keep user anonymity and service provider anonymity, not as claimed. The scheme simply thinks that user anonymity is equivalent to protecting the target user's identity against exposure, while its long-term pseudo-identity can be exposed. We want to clarify that the true anonymity means that an adversary cannot attribute different sessions to different target users, even if the true identifier cannot be retrieved from the exposed pseudo-identifier.
Shiyu Shen, Hao Yang, Wangchen Dai, Lu Zhou, Zhe Liu, Yunlei Zhao
Homomorphic Encryption (HE) enhances data security by facilitating computations on encrypted data, opening new paths for privacy-focused computations. The Brakerski-Fan-Vercauteren (BFV) scheme, a promising HE scheme, raises considerable performance challenges. Graphics Processing Units (GPUs), with considerable parallel processing abilities, have emerged as an effective solution.
In this work, we present an in-depth study focusing on accelerating and comparing BFV variants on GPUs, including Bajard-Eynard-Hasan-Zucca (BEHZ), Halevi-Polyakov-Shoup (HPS), and other recent variants. We introduce a universal framework accommodating all variants, propose optimized BEHZ implementation, and first support HPS variants with large parameter sets on GPUs. Moreover, we devise several optimizations for both low-level arithmetic and high-level operations, including minimizing instructions for modular operations, enhancing hardware utilization for base conversion, implementing efficient reuse strategies, and introducing intra-arithmetic and inner-conversion fusion methods, thus decreasing the overall computational and memory consumption.
Leveraging our framework, we offer comprehensive comparative analyses. Our performance evaluation showcases a marked speed improvement, achieving 31.9× over OpenFHE running on a multi-threaded CPU and 39.7% and 29.9% improvement, respectively, over the state-of-the-art GPU BEHZ implementation. Our implementation of the leveled HPS variant records up to 4× speedup over other variants, positioning it as a highly promising alternative for specific applications.
In this work, we present an in-depth study focusing on accelerating and comparing BFV variants on GPUs, including Bajard-Eynard-Hasan-Zucca (BEHZ), Halevi-Polyakov-Shoup (HPS), and other recent variants. We introduce a universal framework accommodating all variants, propose optimized BEHZ implementation, and first support HPS variants with large parameter sets on GPUs. Moreover, we devise several optimizations for both low-level arithmetic and high-level operations, including minimizing instructions for modular operations, enhancing hardware utilization for base conversion, implementing efficient reuse strategies, and introducing intra-arithmetic and inner-conversion fusion methods, thus decreasing the overall computational and memory consumption.
Leveraging our framework, we offer comprehensive comparative analyses. Our performance evaluation showcases a marked speed improvement, achieving 31.9× over OpenFHE running on a multi-threaded CPU and 39.7% and 29.9% improvement, respectively, over the state-of-the-art GPU BEHZ implementation. Our implementation of the leveled HPS variant records up to 4× speedup over other variants, positioning it as a highly promising alternative for specific applications.
Hao Yang, Shiyu Shen, Siyang Jiang, Lu Zhou, Wangchen Dai, Yunlei Zhao
Homomorphic Encryption (HE) presents a promising solution to securing neural networks for Machine Learning as a Service (MLaaS). Despite its potential, the real-time applicability of current HE-based solutions remains a challenge, and the diversity in network structures often results in inefficient implementations and maintenance. To address these issues, we introduce a unified and compact network structure for real-time inference in convolutional neural networks based on HE. We further propose several optimization strategies, including an innovative compression and encoding technique and rearrangement in the pixel encoding sequence, enabling a highly efficient batched computation and reducing the demand for time-consuming HE operations. To further expedite computation, we propose a GPU acceleration engine to leverage the massive thread-level parallelism to speed up computations. We test our framework with the MNIST, Fashion-MNIST, and CIFAR-10 datasets, demonstrating accuracies of 99.14%, 90.8%, and 61.09%, respectively. Furthermore, our framework maintains a steady processing speed of 0.46 seconds on a single-thread CPU, and a brisk 31.862 milliseconds on an A100 GPU for all datasets. This represents an enhancement in speed more than 3000 times compared to pervious work, paving the way for future explorations in the realm of secure and real-time machine learning applications.
Samuel Coulon, Pengzhou He, Tianyou Bao, Jiafeng Xie
The recently announced National Institute of Standards and Technology (NIST) Post-quantum cryptography (PQC) third-round standardization process has released its candidates to be standardized and Falcon is one of them. On the other hand, however, very few hardware implementation works for Falcon have been released due to its very complicated computation procedure and intensive complexity. With this background, in this paper, we propose an efficient hardware structure to implement residue numeral system (RNS) decomposition within NTRUSolve (a key arithmetic component for key generation of Falcon). In total, we have proposed three stages of coherent interdependent efforts to finish the proposed work. First, we have identified the necessary algorithmic operation related to RNS decomposition. Then, we have innovatively designed a hardware structure to realize these algorithms. Finally, field-programmable gate array (FPGA)-based implementation has been carried out to verify the superior performance of the proposed hardware structure. For instance, the proposed hardware design involves at least 3.91x faster operational time than the software implementation. To the authors' best knowledge, this is the first paper about the hardware acceleration of RNS decomposition for Falcon, and we hope the outcome of this work will facilitate the research in this area.
Aysajan Abidin, Erik Pohle, Bart Preneel
Secure multi-party computation (MPC) enables multiple distrusting parties to compute a function while keeping their respective inputs private. In a threshold implementation of a symmetric primitive, e.g., of a block cipher, each party holds a share of the secret key or of the input block. The output block is computed without reconstructing the secret key. This enables the construction of distributed TPMs or transciphering for secure data transmission in/out of the MPC context.
This paper investigates implementation approaches for the lightweight primitives SKINNY and PHOTON in arithmetic circuits.
For these primitives, we identify arithmetic expressions for the S-box that result in smaller arithmetic circuits compared to the Boolean expressions from the literature.
We validate the optimization using a generic actively secure MPC protocol and obtain 18% faster execution time with 49% less communication data for SKINNY-64-128 and 27% to 74% faster execution time with 49% to 81% less data for PHOTON $P_{100}$ and $P_{288}$.
Furthermore, we find a new set of parameters for the heuristic method of polynomial decomposition, introduced by Coron, Roy and Vivek, specialized for SKINNY's 8-bit S-box. We reduce the multiplicative depth from 9 to 5.
Fernando Virdia
A recent series of works (Hecht, IACR ePrint, 2020–2021) propose to build post-quantum public-key encapsulation, digital signatures, group key agreement and oblivious transfer from "R-propped" variants of the Symmetrical Decomposition and Discrete Logarithm problems for matrix groups over $\mathbb{F}_{2^8}$. We break all four proposals by presenting a linearisation attack on the Symmetrical Decomposition platform, a forgery attack on the signature scheme, and a demonstration of the insecurity of the instances of the Discrete Logarithm Problem used for signatures, group key agreement and oblivious transfer, showing that none of the schemes provides adequate security.
Bala Subramanyan
Amid the landscape of confidential computing, where security and privacy reign supreme, PRIVATON emerges as a pioneering and practical solution to safeguard sensitive data and computations. A verifiable proof of computation model, with one of its variant built upon the dual sandbox strategy, PRIVATON combines Trusted Execution Environment (TEE) technologies with WebAssembly (WASM) runtime environments to establish an ecosystem for privacy-preserving computations. This approach involves fine grained modeling of computations as finite state automatons, guided by verifiable proofs that attest to their unerring execution.
PRIVATON is guided by the profound principles of "least privilege" and "intentional use." Through the former, each computation module's privileges are meticulously constrained, reducing vulnerability vectors. The latter ensures that privileges are allocated explicitly, fostering comprehension and security. This rigorous adherence minimizes privilege misuse and information leakage, bolstering the overall security posture.
At its core, PRIVATON's innovation lies in its comprehensive assurance of data privacy and security. State machine proofs not only attest to the absence of data leakage but also prevent unauthorized data transmission. By providing unassailable proof of computation integrity, PRIVATON shields against code misuse within the system. This proactive stance fortifies its mission to safeguard the sanctity of data, computations, and the privacy of all stakeholders.
Evidenced by its real-world application, PRIVATON has been validated within the cryptocurrency trading ecosystem, where it acts as a distributed and privacy-preserving credit oracle. Its implementation within Credora’s landscape underlines its potential to transform data-centric paradigms, empowering stakeholders with an unshakeable confidence in data security. In a world where data privacy is paramount, PRIVATON stands as a guardian, epitomizing the convergence of technology, security, and trust.
PRIVATON is guided by the profound principles of "least privilege" and "intentional use." Through the former, each computation module's privileges are meticulously constrained, reducing vulnerability vectors. The latter ensures that privileges are allocated explicitly, fostering comprehension and security. This rigorous adherence minimizes privilege misuse and information leakage, bolstering the overall security posture.
At its core, PRIVATON's innovation lies in its comprehensive assurance of data privacy and security. State machine proofs not only attest to the absence of data leakage but also prevent unauthorized data transmission. By providing unassailable proof of computation integrity, PRIVATON shields against code misuse within the system. This proactive stance fortifies its mission to safeguard the sanctity of data, computations, and the privacy of all stakeholders.
Evidenced by its real-world application, PRIVATON has been validated within the cryptocurrency trading ecosystem, where it acts as a distributed and privacy-preserving credit oracle. Its implementation within Credora’s landscape underlines its potential to transform data-centric paradigms, empowering stakeholders with an unshakeable confidence in data security. In a world where data privacy is paramount, PRIVATON stands as a guardian, epitomizing the convergence of technology, security, and trust.
Nina Bindel, Xavier Bonnetain, Marcel Tiepelt, Fernando Virdia
In 2018, Aono et al. (ASIACRYPT 2018) proposed to use quantum backtracking algorithms (Montanaro, TOC 2018; Ambainis and Kokainis, STOC 2017) to speedup lattice point enumeration. Quantum lattice sieving algorithms had already been proposed (Laarhoven et al., PQCRYPTO 2013), being shown to provide an asymptotic speedup over classical counterparts, but also to lose competitivity at relevant dimensions to cryptography if practical considerations on quantum computer architecture were taken into account (Albrecht et al., ASIACRYPT 2020). Aono et al.’s work argued that quantum walk speedups can be applied to lattice enumeration, achieving at least a quadratic asymptotic speedup à la Grover search while not requiring exponential amounts of quantum accessible classical memory, as it is the case for sieving. In this work, we explore how to lower bound the cost of using Aono et al.’s techniques on lattice enumeration with extreme cylinder pruning assuming a limit to the maximum depth that a quantum computation can achieve without decohering, with the objective of better understanding the practical applicability of quantum backtracking in lattice cryptanalysis.
Nilanjan Datta, Avijit Dutta, Samir Kundu
In ASIACRYPT'17, Naito proposed a beyond-birthday-bound variant of the LightMAC construction, called LightMAC_Plus, which is built on three independently keyed $n$-bit block ciphers, and showed that the construction achieves $2n/3$-bits PRF security. Later, Kim et al. claimed (without giving any formal proof) its security bound to $2^{3n/4}$. In FSE'18, Datta et al. have proposed a two-keyed variant of the LightMAC_Plus construction, called 2k-LightMAC_Plus, which is built on two independently keyed $n$-bit block ciphers, and showed that the construction achieves $2n/3$-bits PRF security. In this paper, we show a tight security bound on the 2k-LightMAC_Plus construction. In particular, we show that it provably achieves security up to $2^{3n/4}$ queries. We also exhibit a matching attack on the construction with the same query complexity and hence establishing the tightness of the security bound. To the best of our knowledge, this is the first work that provably shows a message length independent $3n/4$-bit tight security bound on a block cipher based variable input length PRF with two block cipher keys.
Long Chen, Hui Guo, Ya-Nan Li, Qiang Tang
Periodic key rotation is a widely used technique to enhance key compromise resilience. Updatable encryption (UE) schemes provide an efficient approach to key rotation, ensuring post-compromise security for both confidentiality and integrity. However, these UE techniques cannot be directly applied to frequently updated databases due to the risk of a malicious server inducing the client to accept an outdated version of a file instead of the latest one.
To address this issue, we propose a scheme called Updatable Secure Storage (USS), which provides a secure and key updatable solution for dynamic databases. USS ensures both data confidentiality and integrity, even in the presence of key compromises. By using efficient key rotation and file update procedures, the communication costs of these operations are independent of the size of the database. This makes USS particularly well-suited for managing large and frequently updated databases with secure version control. Unlike existing UE schemes, the integrity provided by USS holds even when the server learns the current secret key and intentionally violates the key update protocol.
To address this issue, we propose a scheme called Updatable Secure Storage (USS), which provides a secure and key updatable solution for dynamic databases. USS ensures both data confidentiality and integrity, even in the presence of key compromises. By using efficient key rotation and file update procedures, the communication costs of these operations are independent of the size of the database. This makes USS particularly well-suited for managing large and frequently updated databases with secure version control. Unlike existing UE schemes, the integrity provided by USS holds even when the server learns the current secret key and intentionally violates the key update protocol.
Gil Segev, Amit Sharabi, Eylon Yogev
We propose a new notion of knowledge soundness, denoted rogue-instance security, for interactive and non-interactive batch knowledge proofs. Our notion, inspired by the standard notion of rogue-key security for multi-signature schemes, considers a setting in which a malicious prover is provided with an honestly-generated instance $x_1$, and may then be able to maliciously generate related "rogue" instances $x_2,\ldots,x_k$ for convincing a verifier in a batch knowledge proof of corresponding witnesses $w_1,\ldots,w_k$ for all $k$ instances - without actually having knowledge of the witness $w_1$ corresponding to the honestly-generated instance. This setting provides a powerful security guarantee for batch versions of a wide variety of practically-relevant protocols, such as Schnorr's protocol and similar ones.
We present a highly-efficient generic construction of a batch proof-of-knowledge applicable to any algebraic Sigma protocols. The algebraic property refers to a homomorphic structure of the underlying group and includes Schnorr's protocol and others. We provide an almost tight security analysis for our generic batch protocol, which significantly improves upon the previously known security bounds even for the specific case of batch Schnorr protocol. We extend our results beyond algebraic Sigma protocols. We analyze the rogue-instance security of a general batch protocol with plus-one special soundness (a generalization of standard special soundness) and achieve improved security bounds in the generic case.
Our results use a particular type of high-moment assumptions introduced by Rotem and Segev (CRYPTO 2021). These assumptions consider the hardness of a relation against algorithms with bounded expected running time. Although Rotem and Segev introduced these assumptions, they did not provide evidence to support their hardness. To substantiate and validate the high-moment assumptions, we present a new framework for assessing the concrete hardness of cryptographic problems against oracle algorithms with bounded expected runtime. Our framework covers generic models, including the generic group model, random oracle model, and more. Utilizing our framework, we achieve the first hardness result for these high-moment assumptions. In particular, we establish the second-moment hardness of the discrete-logarithm problem against expected-time algorithms in the generic group model.
We present a highly-efficient generic construction of a batch proof-of-knowledge applicable to any algebraic Sigma protocols. The algebraic property refers to a homomorphic structure of the underlying group and includes Schnorr's protocol and others. We provide an almost tight security analysis for our generic batch protocol, which significantly improves upon the previously known security bounds even for the specific case of batch Schnorr protocol. We extend our results beyond algebraic Sigma protocols. We analyze the rogue-instance security of a general batch protocol with plus-one special soundness (a generalization of standard special soundness) and achieve improved security bounds in the generic case.
Our results use a particular type of high-moment assumptions introduced by Rotem and Segev (CRYPTO 2021). These assumptions consider the hardness of a relation against algorithms with bounded expected running time. Although Rotem and Segev introduced these assumptions, they did not provide evidence to support their hardness. To substantiate and validate the high-moment assumptions, we present a new framework for assessing the concrete hardness of cryptographic problems against oracle algorithms with bounded expected runtime. Our framework covers generic models, including the generic group model, random oracle model, and more. Utilizing our framework, we achieve the first hardness result for these high-moment assumptions. In particular, we establish the second-moment hardness of the discrete-logarithm problem against expected-time algorithms in the generic group model.
Yincen Chen, Nana Zhang, Xuanyu Liang, Ling Song, Qianqian Yang, Zhuohui Feng
GIFT is a family of lightweight block ciphers based on SPN structure and composed of two versions named GIFT-64 and GIFT-128. In this paper, we reevaluate the security of GIFT-64 against the rectangle attack under the related-key setting. Investigating the previous rectangle key recovery attack on GIFT-64, we obtain the core idea of improving the attack——trading off the time complexity of each attack phase. We flexibly guess part of the involved subkey bits to balance the time cost of each phase so that the overall time complexity of the attack is reduced. Moreover, the reused subkey bits are identified according to the linear key schedule of GIFT-64 and bring additional advantages for our attacks. Furthermore, we incorporate the above ideas and propose a dedicated MILP model for finding the best rectangle key recovery attack on GIFT-64. As a result, we get the improved rectangle attacks on 26-round GIFT-64, which are the best attacks on it in terms of time complexity so far.