6154 results sorted by ID
Mempool Privacy via Batched Threshold Encryption: Attacks and Defenses
Arka Rai Choudhuri, Sanjam Garg, Julien Piet, Guru-Vamsi Policharla
Cryptographic protocols
With the rising popularity of DeFi applications it is important to implement protections for regular users of these DeFi platforms against large parties with massive amounts of resources allowing them to engage in market manipulation strategies such as frontrunning/backrunning. Moreover, there are many situations (such as recovery of funds from vulnerable smart contracts) where a user may not want to reveal their transaction until it has been executed. As such, it is clear that preserving...
Agile, Post-quantum Secure Cryptography in Avionics
Karolin Varner, Wanja Zaeske, Sven Friedrich, Aaron Kaiser, Alice Bowman
Cryptographic protocols
To introduce a post-quantum-secure encryption scheme specifically for use in flight-computers, we used avionics’ module-isolation methods to wrap a recent encryption standard (HPKE – Hybrid Public Key Encryption) within a software partition. This solution proposes an upgrade to HPKE, using quantum-resistant ciphers (Kyber/ML-KEM and Dilithium/ML-DSA) redundantly alongside well-established ciphers, to achieve post-quantum security.
Because cryptographic technology can suddenly become...
Homomorphic Evaluation of LWR-based PRFs and Application to Transciphering
Amit Deo, Marc Joye, Benoit Libert, Benjamin R. Curtis, Mayeul de Bellabre
Applications
Certain applications such as FHE transciphering require randomness while operating over encrypted data. This randomness has to be obliviously generated in the encrypted domain and remain encrypted throughout the computation. Moreover, it should be guaranteed that independent-looking random coins can be obliviously generated for different computations.
In this work, we consider the homomorphic evaluation of pseudorandom functions (PRFs) with a focus on practical lattice-based candidates....
Faster Private Decision Tree Evaluation for Batched Input from Homomorphic Encryption
Kelong Cong, Jiayi Kang, Georgio Nicolas, Jeongeun Park
Applications
Privacy-preserving decision tree evaluation (PDTE) allows a client that holds feature vectors to perform inferences against a decision tree model on the server side without revealing feature vectors to the server. Our work focuses on the non-interactive batched setting where the client sends a batch of encrypted feature vectors and then obtains classifications, without any additional interaction. This is useful in privacy-preserving credit scoring, biometric authentication, and many more...
FE[r]Chain: Enforcing Fairness in Blockchain Data Exchanges Through Verifiable Functional Encryption
Camille Nuoskala, Reyhaneh Rabbaninejad, Tassos Dimitriou, Antonis Michalas
Cryptographic protocols
Functional Encryption (FE) allows users to extract specific function-related information from encrypted data while preserving the privacy of the underlying plaintext. Though significant research has been devoted to developing secure and efficient Multi-Input Functional Encryption schemes supporting diverse functions, there remains a noticeable research gap in the development of verifiable FE schemes. Functionality and performance have received considerable attention, however, the crucial...
Monchi: Multi-scheme Optimization For Collaborative Homomorphic Identification
Alberto Ibarrondo, Ismet Kerenciler, Hervé Chabanne, Vincent Despiegel, Melek Önen
Cryptographic protocols
This paper introduces a novel protocol for privacy-preserving biometric identification, named Monchi, that combines the use of homomorphic encryption for the computation of the identification score with function secret sharing to obliviously compare this score with a given threshold and finally output the binary result. Given the cost of homomorphic encryption, BFV in this solution, we study and evaluate the integration of two packing solutions that enable the regrouping of multiple...
Encrypted KNN Implementation on Distributed Edge Device Network
B Pradeep Kumar Reddy, Ruchika Meel, Ayantika Chatterjee
Applications
Machine learning (ML) as a service has emerged as a rapidly expanding field across various industries like
healthcare, finance, marketing, retail and e-commerce, Industry 4.0, etc where a huge amount of data is gen-
erated. To handle this amount of data, huge computational power is required for which cloud computing used
to be the first choice. However, there are several challenges in cloud computing like limitations of bandwidth,
network connectivity, higher latency, etc. To address...
Toward Independent Key Encryption based on Q-Problem
Abdelkader Laouid, Mostefa Kara, Mohammad Hammoudeh
Cryptographic protocols
This paper defines a post-quantum encryption scheme based on discussion cryptography by introducing a new post-quantum hard problem called Q-Problem. The idea behind this scheme is to hide the keys of each entity, and the encryption process is based on secret message holders using only random private keys.
Organizing Records for Retrieval in Multi-Dimensional Range Searchable Encryption
Mahdieh Heidaripour, Ladan Kian, Maryam Rezapour, Mark Holcomb, Benjamin Fuller, Gagan Agrawal, Hoda Maleki
Applications
Storage of sensitive multi-dimensional arrays must be secure and efficient in storage and processing time. Searchable encryption allows one to trade between security and efficiency. Searchable encryption design focuses on building indexes, overlooking the crucial aspect of record retrieval. Gui et al. (PoPETS 2023) showed that understanding the security and efficiency of record retrieval is critical to understand the overall system. A common technique for improving security is partitioning...
NTRU-based FHE for Larger Key and Message Space
Robin Jadoul, Axel Mertens, Jeongeun Park, Hilder V. L. Pereira
Public-key cryptography
The NTRU problem has proven a useful building block for efficient bootstrapping in Fully Homomorphic Encryption (FHE) schemes, and different such schemes have been proposed. FINAL (ASIACRYPT 2022) first constructed FHE using homomorphic multiplexer (CMux) gates for the blind rotation operation. Later, XZD+23 (CRYPTO 2023) gave an asymptotic optimization by changing the ciphertext format to enable ring automorphism evaluations. In this work, we examine an adaptation to FINAL to evaluate CMux...
MUSEN: Aggregatable Key-Evolving Verifiable Random Functions and Applications
Bernardo David, Rafael Dowsley, Anders Konring, Mario Larangeira
Cryptographic protocols
A Verifiable Random Function (VRF) can be evaluated on an input by a prover who holds a secret key, generating a pseudorandom output and a proof of output validity that can be verified using the corresponding public key. VRFs are a central building block of committee election mechanisms that sample parties to execute tasks in cryptographic protocols, e.g. generating blocks in a Proof-of-Stake (PoS) blockchain or executing a round of MPC protocols. We propose the notion, and a matching...
Distributed & Scalable Oblivious Sorting and Shuffling
Nicholas Ngai, Ioannis Demertzis, Javad Ghareh Chamani, Dimitrios Papadopoulos
Cryptographic protocols
Existing oblivious systems offer robust security by concealing memory access patterns, but they encounter significant scalability and performance challenges. Recent efforts to enhance the practicality of these systems involve embedding oblivious computation, e.g., oblivious sorting and shuffling, within Trusted Execution Environments (TEEs). For instance, oblivious sort has been heavily utilized: in Oblix (S&P'18), when oblivious indexes are created and accessed; in Snoopy's high-throughput...
New SAT-based Model for Quantum Circuit Decision Problem: Searching for Low-Cost Quantum Implementation
Jingwen Chen, Qun Liu, Yanhong Fan, Lixuan Wu, Boyun Li, Meiqin Wang
Implementation
In recent years, quantum technology has been rapidly developed. As security analyses for symmetric ciphers continue to emerge, many require an evaluation of the resources needed for the quantum circuit implementation of the encryption algorithm. In this regard, we propose the quantum circuit decision problem, which requires us to determine whether there exists a quantum circuit for a given permutation f using M ancilla qubits and no more than K quantum gates within the circuit depth D....
BPDTE: Batch Private Decision Tree Evaluation via Amortized Efficient Private Comparison
Huiqiang Liang, Haining Lu, Geng Wang
Applications
Machine learning as a service requires the client to trust the server and provide its own private information to use this service. Usually, clients may worry that their private data is being collected by server without effective supervision, and the server also aims to ensure proper management of the user data to foster the advancement of its services. In this work, we focus on private decision tree evaluation (PDTE) which can alleviates such privacy concerns associated with classification...
Non-interactive Blind Signatures from Lattices
Foteini Baldimtsi, Jiaqi Cheng, Rishab Goyal, Aayush Yadav
Public-key cryptography
Blind signatures enable a receiver to obtain signatures on messages of its choice without revealing any message to the signer. Round-optimal blind signatures are designed as a two-round interactive protocol between a signer and receiver. Coincidentally, the choice of message is not important in many applications, and is routinely set as a random (unstructured) message by a receiver.
With the goal of designing more efficient blind signatures for such applications, Hanzlik (Eurocrypt '23)...
FHERMA: Building the Open-Source FHE Components Library for Practical Use
Gurgen Arakelov, Nikita Kaskov, Daria Pianykh, Yuriy Polyakov
Applications
Fully Homomorphic Encryption (FHE) is a powerful Privacy-Enhancing Technology (PET) that enables computations on encrypted data without having access to the secret key. While FHE holds immense potential for enhancing data privacy and security, creating its practical applications is associated with many difficulties. A significant barrier is the absence of easy-to-use, standardized components that developers can utilize as foundational building blocks. Addressing this gap requires...
A Characterization of AE Robustness as Decryption Leakage Indistinguishability
Ganyuan Cao
Secret-key cryptography
Robustness has emerged as an important criterion for authenticated encryption, alongside the requirements of confidentiality and integrity. We introduce a novel notion, denoted as IND-rCCA, to formalize the robustness of authenticated encryption from the perspective of decryption leakage. This notion is an augmentation of common notions defined for AEAD schemes by considering indistinguishability of potential leakage due to decryption failure, particularly in the presence of multiple checks...
Analysis of Multivariate Encryption Schemes: Application to Dob and C*
Morten Øygarden, Patrick Felke, Håvard Raddum
Attacks and cryptanalysis
A common strategy for constructing multivariate encryption schemes is to use a central map that is easy to invert over an extension field, along with a small number of modifications to thwart potential attacks. In this work we study the effectiveness of these modifications, by deriving estimates for the number of degree fall polynomials. After developing the necessary tools, we focus on encryption schemes using the $C^*$ and Dobbertin central maps, with the internal perturbation (ip), and...
Greco: Fast Zero-Knowledge Proofs for Valid FHE RLWE Ciphertexts Formation
Enrico Bottazzi
Cryptographic protocols
Fully homomorphic encryption (FHE) allows for evaluating arbitrary functions over encrypted data. In Multi-party FHE applications, different parties encrypt their secret data and submit ciphertexts to a server, which, according to the application logic, performs homomorphic operations on them. For example, in a secret voting application, the tally is computed by summing up the ciphertexts encoding the votes. Valid encrypted votes are of the form $E(0)$ and $E(1)$. A malicious voter could...
The Case of Small Prime Numbers Versus the Okamoto-Uchiyama Cryptosystem
George Teseleanu
Public-key cryptography
In this paper we study the effect of using small prime numbers within the Okamoto-Uchiyama public key encryption scheme. We introduce two novel versions and prove their security. Then we show how to choose the system's parameters such that the security results hold. Moreover, we provide a practical comparison between the cryptographic algorithms we introduced and the original Okamoto-Uchiyama cryptosystem.
Encryption Based Covert Channel for Large Language Models
Yongge Wang
Applications
Transformer neural networks have gained significant traction since their introduction, becoming pivotal across diverse domains. Particularly in large language models like Claude and ChatGPT, the transformer architecture has demonstrated remarkable efficacy. This paper provides a concise overview of transformer neural networks and delves into their security considerations, focusing on covert channel attacks and their implications for the safety of large language models. We present a covert...
A Complete Beginner Guide to the Number Theoretic Transform (NTT)
Ardianto Satriawan, Rella Mareta, Hanho Lee
Foundations
The Number Theoretic Transform (NTT) is a powerful mathematical tool that has become increasingly important in developing Post Quantum Cryptography (PQC) and Homomorphic Encryption (HE). Its ability to efficiently calculate polynomial multiplication using the convolution theorem with a quasi-linear complexity $O(n \log{n})$ instead of $O(n^2)$ when implemented with Fast Fourier Transform-style algorithms has made it a key component in modern cryptography. FFT-style NTT algorithm or fast-NTT...
Dynamic Decentralized Functional Encryptions from Pairings in the Standard Model
Duy Nguyen
Cryptographic protocols
Dynamic Decentralized Functional Encryption (DDFE), introduced by Chotard et al. (CRYPTO'20), stands as a robust generalization of (Multi-Client) Functional Encryption. It enables users to dynamically join and contribute private inputs to individually-controlled joint functions, all without requiring a trusted authority. Agrawal et al. (TCC’21) further extended this line of research by presenting the first DDFE construction for function-hiding inner products (FH-IP-DDFE) in the random oracle...
Tokenised Multi-client Provisioning for Dynamic Searchable Encryption with Forward and Backward Privacy
Arnab Bag, Sikhar Patranabis, Debdeep Mukhopadhyay
Applications
Searchable Symmetric Encryption (SSE) has opened up an attractive avenue for privacy-preserved processing of outsourced data on the untrusted cloud infrastructure. SSE aims to support efficient Boolean query processing with optimal storage and search overhead over large real databases. However, current constructions in the literature lack the support for multi-client search and dynamic updates to the encrypted databases, which are essential requirements for the widespread deployment of SSE...
A Note on Related-Tweakey Impossible Differential Attacks
Xavier Bonnetain, Virginie Lallemand
Attacks and cryptanalysis
In this short note we review the technique proposed at ToSC 2018 by Sadeghi et al. for attacks built upon several related-tweakey impossible differential trails. We show that the initial encryption queries are improper and lead the authors to misevaluating a filtering value in the key recovery phase. We identified 4 papers (from Eurocrypt, DCC, ToSC and ePrint) that follow on the results of Sadeghi et al., and in three of them the issue was propagated.
We thus present a careful analysis of...
Two-Party Decision Tree Training from Updatable Order-Revealing Encryption
Robin Berger, Felix Dörre, Alexander Koch
Cryptographic protocols
Running machine learning algorithms on encrypted data is a way forward to marry functionality needs common in industry with the important concerns for privacy when working with potentially sensitive data. While there is already a growing field on this topic and a variety of protocols, mostly employing fully homomorphic encryption or performing secure multiparty computation (MPC), we are the first to propose a protocol that makes use of a specialized encryption scheme that allows to do secure...
Convolution-Friendly Image Compression in FHE
Axel Mertens, Georgio Nicolas, Sergi Rovira
Applications
Fully Homomorphic Encryption (FHE) is a powerful tool that brings privacy and security to all sorts of applications by allowing us to perform additions and multiplications directly on ciphertexts without the need of the secret key.
Some applications of FHE that were previously overlooked but have recently been gaining traction are data compression and image processing.
Practically, FHE enables applications such as private satellite searching,
private object recognition, or even encrypted...
Leakage-Abuse Attacks Against Structured Encryption for SQL
Alexander Hoover, Ruth Ng, Daren Khu, Yao'an Li, Joelle Lim, Derrick Ng, Jed Lim, Yiyang Song
Attacks and cryptanalysis
Structured Encryption (StE) enables a client to securely store and query data stored on an untrusted server. Recent constructions of StE have moved beyond basic queries, and now support large subsets of SQL. However, the security of these constructions is poorly understood, and no systematic analysis has been performed.
We address this by providing the first leakage-abuse attacks against StE for SQL schemes. Our attacks can be run by a passive adversary on a server with access to some...
Fast Parallelizable Misuse-Resistant Authenticated Encryption: Low Latency (Decryption-Fast) SIV
Mustafa Khairallah
Secret-key cryptography
MRAE security is an important goal for many AEAD applications where the nonce uniqueness cannot be maintained and security risks are significant. However, MRAE schemes can be quite expensive. Two of the SoTA MRAE-secure schemes; Deoxys-II and AES-GCM-SIV rely on internal parallelism and special instructions to achieve competitive performance. However, they both suffer from the same bottleneck, they have at least one call to the underlying primitive that cannot be parallelized to any other...
Integral Attack on the Full FUTURE Block Cipher
Zeyu Xu, Jiamin Cui, Kai Hu, Meiqin Wang
Attacks and cryptanalysis
FUTURE is a recently proposed lightweight block cipher that achieved a remarkable hardware performance due to careful design decisions. FUTURE is an Advanced Encryption Standard (AES)-like Substitution-Permutation Network (SPN) with 10 rounds, whose round function consists of four components, i.e., SubCell, MixColumn, ShiftRow and AddRoundKey. Unlike AES, it is a 64-bit-size block cipher with a 128-bit secret key, and the state can be arranged into 16 cells. Therefore, the operations of...
Share with Care: Breaking E2EE in Nextcloud
Martin R. Albrecht, Matilda Backendal, Daniele Coppola, Kenneth G. Paterson
Attacks and cryptanalysis
Nextcloud is a leading cloud storage platform with more than 20 million users.
Nextcloud offers an end-to-end encryption (E2EE) feature that is claimed to be able “to keep extremely sensitive data fully secure even in case of a full server breach”.
They also claim that the Nextcloud server “has Zero Knowledge, that is, never has access to any of the data or keys in unencrypted form”.
This is achieved by having encryption and decryption operations that are done using file keys that are...
Fully Homomorphic Training and Inference on Binary Decision Tree and Random Forest
Hojune Shin, Jina Choi, Dain Lee, Kyoungok Kim, Younho Lee
This paper introduces a new method for training decision trees and random forests using CKKS homomorphic encryption (HE) in cloud environments, enhancing data privacy from multiple sources. The innovative Homomorphic Binary Decision Tree (HBDT) method utilizes a modified Gini Impurity index (MGI) for node splitting in encrypted data scenarios. Notably, the proposed training approach operates in a single cloud security domain without the need for decryption, addressing key challenges in...
LIT-SiGamal: An efficient isogeny-based PKE based on a LIT diagram
Tomoki Moriya
Public-key cryptography
In this paper, we propose a novel isogeny-based public key encryption (PKE) scheme named LIT-SiGamal. This is based on a LIT diagram and SiGamal. SiGamal is an isogeny-based PKE scheme that uses a commutative diagram with an auxiliary point. LIT-SiGamal uses a LIT diagram which is a commutative diagram consisting of large-degree horizontal isogenies and relatively small-degree vertical isogenies, while the original SiGamal uses a CSIDH diagram.
A strength of LIT-SiGamal is efficient...
Similar Data is Powerful: Enhancing Inference Attacks on SSE with Volume Leakages
Björn Ho, Huanhuan Chen, Zeshun Shi, Kaitai Liang
Applications
Searchable symmetric encryption (SSE) schemes provide users with the ability to perform keyword searches on encrypted databases without the need for decryption. While this functionality is advantageous, it introduces the potential for inadvertent information disclosure, thereby exposing SSE systems to various types of attacks. In this work, we introduce a new inference attack aimed at enhancing the query recovery accuracy of RefScore (presented at USENIX 2021). The proposed approach...
Inject Less, Recover More: Unlocking the Potential of Document Recovery in Injection Attacks Against SSE
Manning Zhang, Zeshun Shi, Huanhuan Chen, Kaitai Liang
Applications
Searchable symmetric encryption has been vulnerable to inference attacks that rely on uniqueness in leakage patterns. However, many keywords in datasets lack distinctive leakage patterns, limiting the effectiveness of such attacks. The file injection attacks, initially proposed by Cash et al. (CCS 2015), have shown impressive performance with 100% accuracy and no prior knowledge requirement. Nevertheless, this attack fails to recover queries with underlying keywords not present in the...
Quantum Implementation and Analysis of SHA-2 and SHA-3
Kyungbae Jang, Sejin Lim, Yujin Oh, Hyunjun Kim, Anubhab Baksi, Sumanta Chakraborty, Hwajeong Seo
Implementation
Quantum computers have the potential to solve hard problems that are nearly impossible to solve by classical computers, this has sparked a surge of research to apply quantum technology and algorithm against the cryptographic systems to evaluate for its quantum resistance. In the process of selecting post-quantum standards, NIST categorizes security levels based on the complexity that quantum computers would require to crack AES encryption (levels 1, 3 and 5) and SHA-2 or SHA-3 (levels 2 and...
A Black-box Attack on Fixed-Unitary Quantum Encryption Schemes
Cezary Pilaszewicz, Lea R. Muth, Marian Margraf
Attacks and cryptanalysis
We show how fixed-unitary quantum encryption schemes can be attacked in a black-box setting. We use an efficient technique to invert a unitary transformation on a quantum computer to retrieve an encrypted secret quantum state $\ket{\psi}$. This attack has a success rate of 100% and can be executed in constant time. We name a vulnerable scheme and suggest how to improve it to invalidate this attack. The proposed attack highlights the importance of carefully designing quantum encryption...
DoS-resistant Oblivious Message Retrieval from Snake-eye Resistant PKE
Zeyu Liu, Katerina Sotiraki, Eran Tromer, Yunhao Wang
Oblivious message retrieval (OMR) allows messages resource-limited recipients to outsource the message retrieval process without revealing which messages are pertinent to which recipient. Its realizations in recent works leave an open problem: can an OMR scheme be both practical and provably secure against spamming attacks from malicious senders (i.e., DoS-resistant) under standard assumptions?
In this paper, we first prove that a prior construction OMRp2 is DoS-resistant under a...
A Decentralized Federated Learning using Reputation
Olive Chakraborty, Aymen Boudguiga
Applications
Nowadays Federated learning (FL) is established as one of the best techniques for collaborative machine learning. It allows a set of clients to train a common model without disclosing their sensitive and private
dataset to a coordination server. The latter is in charge of the model aggregation. However, FL faces some problems, regarding the security of updates, integrity of computation and the availability of a server.
In this paper, we combine some new ideas like clients’ reputation with...
Anonymous Revocable Identity-Based Encryption Supporting Anonymous Revocation
Kwangsu Lee
Public-key cryptography
Anonymous identity-based encryption (AIBE) is an extension of identity-based encryption (IBE) that enhances the privacy of a ciphertext by providing ciphertext anonymity. In this paper, we introduce the concept of revocable IBE with anonymous revocation (RIBE-AR), which is capable of issuing an update key and hiding the revoked set of the update key that efficiently revokes private keys of AIBE. We first define the security models of RIBE-AR and propose an efficient RIBE-AR scheme in...
CCA Secure Updatable Encryption from Non-Mappable Group Actions
Jonas Meers, Doreen Riepel
Cryptographic protocols
Ciphertext-independent updatable encryption (UE) allows to rotate encryption keys and update ciphertexts via a token without the need to first download the ciphertexts. Although, syntactically, UE is a symmetric-key primitive, ciphertext-independent UE with forward secrecy and post-compromise security is known to imply public-key encryption (Alamati, Montgomery and Patranabis, CRYPTO 2019).
Constructing post-quantum secure UE turns out to be a difficult task. While lattices offer the...
Number-Theoretic Transform Architecture for Fully Homomorphic Encryption from Hypercube Topology
Jingwei Hu, Yuhong Fang, Wangchen Dai
Implementation
This paper introduces a high-performance and scalable hardware architecture designed for the Number-Theoretic Transform (NTT), a fundamental component extensively utilized in lattice-based encryption and fully homomorphic encryption schemes.
The underlying rationale behind this research is to harness the advantages of the hypercube topology. This topology serves to significantly diminish the volume of data exchanges required during each iteration of the NTT, reducing it to a complexity of...
On the Security of Data Markets and Private Function Evaluation
István Vajda
Cryptographic protocols
The income of companies working on data markets steadily grows year by year. Private function evaluation (PFE) is a valuable tool in solving corresponding security problems. The task of Controlled Private Function Evaluation and its relaxed version was introduced in [Horvath et.al., 2019]. In this article, we propose and examine several different approaches for such tasks with computational and information theoretical security against static corruption adversary. The latter level of security...
Two-Round Threshold Signature from Algebraic One-More Learning with Errors
Thomas Espitau, Shuichi Katsumata, Kaoru Takemure
Cryptographic protocols
Threshold signatures have recently seen a renewed interest due to applications in cryptocurrency while NIST has released a call for multi-party threshold schemes, with a deadline for submission expected for the first half of 2025. So far, all lattice-based threshold signatures requiring less than two-rounds are based on heavy tools such as (fully) homomorphic encryption (FHE) and homomorphic trapdoor commitments (HTDC). This is not unexpected considering that most efficient two-round...
Updatable Policy-Compliant Signatures
Christian Badertscher, Monosij Maitra, Christian Matt, Hendrik Waldner
Cryptographic protocols
Policy-compliant signatures (PCS) are a recently introduced primitive by Badertscher et
al. [TCC 2021] in which a central authority distributes secret and public keys associated with sets of attributes (e.g., nationality, affiliation with a specific department, or age) to its users. The authority also enforces a policy determining which senders can sign messages for which receivers based on a joint check of their attributes. For example, senders and receivers must have the same nationality,...
Improving Generic Attacks Using Exceptional Functions
Xavier Bonnetain, Rachelle Heim Boissier, Gaëtan Leurent, André Schrottenloher
Attacks and cryptanalysis
Over the past ten years, the statistical properties of random functions have been particularly fruitful for generic attacks. Initially, these attacks targeted iterated hash constructions and their combiners, developing a wide array of methods based on internal collisions and on the average behavior of iterated random functions. More recently, Gilbert et al. (EUROCRYPT 2023) introduced a forgery attack on so-called duplex-based Authenticated Encryption modes which was based on exceptional...
Anamorphic Encryption: New Constructions and Homomorphic Realizations
Dario Catalano, Emanuele Giunta, Francesco Migliaro
Public-key cryptography
The elegant paradigm of Anamorphic Encryption (Persiano et al., Eurocrypt 2022) considers the question of establishing a private communication in a world controlled by a dictator.
The challenge is to allow two users, sharing some secret anamorphic key, to exchange covert messages without the dictator noticing, even when the latter has full access to the regular secret keys.
Over the last year several works considered this question and proposed constructions, novel extensions and...
Lower data attacks on Advanced Encryption Standard
Orhun Kara
Secret-key cryptography
The Advanced Encryption Standard (AES) is one of the most commonly used and analyzed encryption algorithms. In this work, we present new combinations of some prominent attacks on AES, achieving new records in data requirements among attacks, utilizing only $2^4$ and $2^{16}$ chosen plaintexts (CP) for 6-round and 7-round AES-192/256 respectively. One of our attacks is a combination of a meet-in-the-middle (MiTM) attack with a square attack mounted on 6-round AES-192/256 while ...
Fast Secure Computations on Shared Polynomials and Applications to Private Set Operations
Pascal Giorgi, Fabien Laguillaumie, Lucas Ottow, Damien Vergnaud
Cryptographic protocols
Secure multi-party computation aims to allow a set of players to compute a given function on their secret inputs without revealing any other information than the result of the computation. In this work, we focus on the design of secure multi-party protocols for shared polynomial operations. We consider the classical model where the adversary is honest-but-curious, and where the coefficients (or any secret values) are either encrypted using an additively homomorphic encryption scheme or...
Partially Non-Interactive Two-Round Lattice-Based Threshold Signatures
Rutchathon Chairattana-Apirom, Stefano Tessaro, Chenzhi Zhu
Cryptographic protocols
This paper gives the first lattice-based two-round threshold signature based on lattice assumptions for which the first message is independent of the message being signed without relying on fully-homomorphic encryption, and our construction supports arbitrary thresholds.
Our construction provides a careful instantiation of a generic threshold signature construction by Tessaro and Zhu (EUROCRYPT ’23) based on specific linear hash functions, which in turns can be seen as a generalization of...
Security Guidelines for Implementing Homomorphic Encryption
Jean-Philippe Bossuat, Rosario Cammarota, Jung Hee Cheon, Ilaria Chillotti, Benjamin R. Curtis, Wei Dai, Huijing Gong, Erin Hales, Duhyeong Kim, Bryan Kumara, Changmin Lee, Xianhui Lu, Carsten Maple, Alberto Pedrouzo-Ulloa, Rachel Player, Luis Antonio Ruiz Lopez, Yongsoo Song, Donggeon Yhee, Bahattin Yildiz
Attacks and cryptanalysis
Fully Homomorphic Encryption (FHE) is a cryptographic primitive that allows performing arbitrary operations on encrypted data. Since the conception of the idea in [RAD78], it was considered a holy grail of cryptography. After the first construction in 2009 [Gen09], it has evolved to become a practical primitive with strong security guarantees. Most modern constructions are based on well-known lattice problems such as Learning with Errors (LWE). Besides its academic appeal, in recent years...
Encrypted Image Classification with Low Memory Footprint using Fully Homomorphic Encryption
Lorenzo Rovida, Alberto Leporati
Applications
Classifying images has become a straightforward and accessible task, thanks to the advent of Deep Neural Networks. Nevertheless, not much attention is given to the privacy concerns associated with sensitive data contained in images. In this study, we propose a solution to this issue by exploring an intersection between Machine Learning and cryptography.
In particular, Fully Homomorphic Encryption (FHE) emerges as a promising solution, as it enables computations to be performed on encrypted...
Studying Lattice-Based Zero-Knowlege Proofs: A Tutorial and an Implementation of Lantern
Lena Heimberger, Florian Lugstein, Christian Rechberger
Implementation
Lattice-based cryptography has emerged as a promising new candidate to build cryptographic primitives. It offers resilience against quantum attacks, enables fully homomorphic encryption, and relies on robust theoretical foundations. Zero-knowledge proofs (ZKPs) are an essential primitive for various privacy-preserving applications. For example, anonymous credentials, group signatures, and verifiable oblivious pseudorandom functions all require ZKPs. Currently, the majority of ZKP systems are...
The 2Hash OPRF Framework and Efficient Post-Quantum Instantiations
Ward Beullens, Lucas Dodgson, Sebastian Faller, Julia Hesse
Cryptographic protocols
An Oblivious Pseudo-Random Function (OPRF) is a two-party protocol for jointly evaluating a Pseudo-Random Function (PRF), where a user has an input x and a server has an input k. At the end of the protocol, the user learns the evaluation of the PRF using key k at the value x, while the server learns nothing about the user's input or output.
OPRFs are a prime tool for building secure authentication and key exchange from passwords, private set intersection, private information retrieval,...
ORIGO: Proving Provenance of Sensitive Data with Constant Communication
Jens Ernstberger, Jan Lauinger, Yinnan Wu, Arthur Gervais, Sebastian Steinhorst
Applications
Transport Layer Security ( TLS ) is foundational for safeguarding client-server communication. However, it does not extend integrity guarantees to third-party verification of data authenticity. If a client wants to present data obtained from a server, it cannot convince any other party that the data has not been tampered with.
TLS oracles ensure data authenticity beyond the client-server TLS connection, such that clients can obtain data from a server and ensure provenance to any third...
The cool and the cruel: separating hard parts of LWE secrets
Niklas Nolte, Mohamed Malhou, Emily Wenger, Samuel Stevens, Cathy Yuanchen Li, Francois Charton, Kristin Lauter
Attacks and cryptanalysis
Sparse binary LWE secrets are under consideration for standardization for Homomorphic Encryption and its applications to private computation. Known attacks on sparse binary LWE secrets include the sparse dual attack and the hybrid sparse dual-meet in the middle attack, which requires significant memory. In this paper, we provide a new statistical attack with low memory requirement. The attack relies on some initial parallelized lattice reduction. The key observation is that, after...
Fastcrypto: Pioneering Cryptography Via Continuous Benchmarking
Kostas Kryptos Chalkias, Jonas Lindstrøm, Deepak Maram, Ben Riva, Arnab Roy, Alberto Sonnino, Joy Wang
Implementation
In the rapidly evolving fields of encryption and blockchain technologies, the efficiency and security of cryptographic schemes significantly impact performance. This paper introduces a comprehensive framework for continuous benchmarking in one of the most popular cryptography Rust libraries, fastcrypto. What makes our analysis unique is the realization that automated benchmarking is not just a performance monitor and optimization tool, but it can be used for cryptanalysis and innovation...
Parameter-Hiding Order-Revealing Encryption without Pairings
Cong Peng, Rongmao Chen, Yi Wang, Debiao He, Xinyi Huang
Cryptographic protocols
Order-Revealing Encryption (ORE) provides a practical solution for conducting range queries over encrypted data. Achieving a desirable privacy-efficiency tradeoff in designing ORE schemes has posed a significant challenge. At Asiacrypt 2018, Cash et al. proposed Parameter-hiding ORE (pORE), which specifically targets scenarios where the data distribution shape is known, but the underlying parameters (such as mean and variance) need to be protected. However, existing pORE constructions rely...
On the Concrete Security of Approximate FHE with Noise-Flooding Countermeasures
Flavio Bergamaschi, Anamaria Costache, Dana Dachman-Soled, Hunter Kippen, Lucas LaBuff, Rui Tang
Attacks and cryptanalysis
Approximate fully homomorphic encryption (FHE) schemes such as the CKKS scheme (Asiacrypt '17) are popular in practice due to their efficiency and utility for machine learning applications. Unfortunately, Li and Micciancio (Eurocrypt, '21) showed that, while achieving standard semantic (or $\mathsf{IND}\mbox{-}\mathsf{CPA}$ security), the CKKS scheme is broken under a variant security notion known as $\mathsf{IND}\mbox{-}\mathsf{CPA}^D$. Subsequently, Li, Micciancio, Schultz, and Sorrell...
Atomic and Fair Data Exchange via Blockchain
Ertem Nusret Tas, István András Seres, Yinuo Zhang, Márk Melczer, Mahimna Kelkar, Joseph Bonneau, Valeria Nikolaenko
Cryptographic protocols
We introduce a blockchain Fair Data Exchange (FDE) protocol, enabling a storage server to transfer a data file to a client atomically: the client receives the file if and only if the server receives an agreed-upon payment. We put forth a new definition for a cryptographic scheme that we name verifiable encryption under committed key (VECK), and we propose two instantiations for this scheme. Our protocol relies on a blockchain to enforce the atomicity of the exchange and uses VECK to ensure...
An improved exact CRR basis conversion algorithm for FHE without floating-point arithmetic
Hongyuan Qu, Guangwu Xu
Public-key cryptography
Fully homomorphic encryption (FHE) has attracted much attention recently. Chinese remainder representation (CRR) or RNS representation is one of the core technologies of FHE. CRR basis conversion is a key step of KeySwitching procedure. Bajard et al. proposed a fast basis conversion method for CRR basis conversion, but the elimination of error had to be ignored. Halevi et al. suggested a method using floating-point arithmetic to avoid errors, but floating-point arithmetic has its own issues...
Breaking the DECT Standard Cipher with Lower Time Cost
Lin Ding, Zhengting Li, Ziyu Guan, Xinhai Wang, Zheng Wu
Attacks and cryptanalysis
The DECT Standard Cipher (DSC) is a proprietary stream cipher used for encryption in the Digital Enhanced Cordless Telecommunications (DECT), which is a standard for short range cordless communication and widely deployed worldwide both in residential and enterprise environments. New weaknesses of the DSC stream cipher which are not discovered in previous works are explored and analyzed in this paper. Based on these weaknesses, new practical key recovery attacks and distinguishing attack on...
Efficient Unbalanced Quorum PSI from Homomorphic Encryption
Xinpeng Yang, Liang Cai, Yinghao Wang, Yinghao Wang, Lu Sun, Jingwei Hu
Cryptographic protocols
Multiparty private set intersection (mPSI) protocol is capable of finding the intersection of multiple sets securely without revealing any other information. However, its limitation lies in processing only those elements present in every participant's set, which proves inadequate in scenarios where certain elements are common to several, but not all, sets.
In this paper, we introduce an innovative variant of the mPSI protocol named unbalanced quorum PSI to fill in the gaps of the mPSI...
SILBE: an Updatable Public Key Encryption Scheme from Lollipop Attacks
Max Duparc, Tako Boris Fouotsa, Serge Vaudenay
Public-key cryptography
We present a new post-quantum Public Key Encryption scheme (PKE) named Supersingular Isogeny Lollipop Based Encryption or SILBE. SILBE is obtained by leveraging the generalized lollipop attack of Castryck and Vercauteren on the M-SIDH Key exchange by Fouotsa, Moriya and Petit. Doing so, we can in fact make of SILBE a post-quantum secure Updatable Public Key Encryption scheme (UPKE). SILBE is the first isogeny-based UPKE which is not based on group actions. In its core, SILBE extensively...
Exponent-VRFs and Their Applications
Dan Boneh, Iftach Haitner, Yehuda Lindell
Public-key cryptography
Verifiable random functions (VRFs) are pseudorandom functions with the addition that the function owner can prove that a generated output is correct, with respect to a committed key. In this paper we introduce the notion of an exponent-VRF, or eVRF, which is a VRF that does not provide its output $y$ explicitly, but instead provides $Y = y \cdot G$, where $G$ is a generator of some finite cyclic group (or $Y = g^y$ in multiplicative notation). We construct eVRFs from DDH and from the...
A Deniably Authenticated Searchable Public Key Encryption Scheme in Mobile Electronic Mail System
Shuhan Zeng, Yongjian Liao, Chuanhao Zhou, Jinlin He, Hongwei Wang
Public-key cryptography
Confidentiality and authentication are two main security goals in secure electronic mail (e-mail). Furthermore, deniability is also a significant security property for some e-mail applications to protect the privacy of the sender. Although searchable encryption solves the keyword searching problem in a secure e-mail system, it also breaks the deniability of the system. Because the adversary can obtain the information of the data sender and data user from the trapdoor as well as ciphertext...
Leakage-Resilient Attribute-Based Encryption with Attribute-Hiding
Yijian Zhang, Yunhao Ling, Jie Chen, Luping Wang
Public-key cryptography
In this work, we present two generic frameworks for leakage-resilient attribute-based encryption (ABE), which is an improved version of ABE that can be proven secure even when part of the secret key is leaked. Our frameworks rely on the standard assumption ($k$-Lin) over prime-order groups. The first framework is designed for leakage-resilient ABE with attribute-hiding in the bounded leakage model. Prior to this work, no one had yet derived a generic leakage-resilient ABE framework with...
Decentralized Access Control Infrastructure for Enterprise Digital Asset Management
Chirag Madaan, Rohan Agarwal, Vipul Saini, Ujjwal Kumar
Cryptographic protocols
With the rapidly evolving landscape of cryptography, blockchain technology has advanced to cater to diverse user requirements, leading to the emergence of a multi-chain ecosystem featuring various use cases characterized by distinct transaction speed and decentralization trade-offs. At the heart of this evolution lies digital signature schemes, responsible for safeguarding blockchain-based assets such as ECDSA, Schnorr, and EdDSA, among others.
However, a critical gap exists in the...
Quantum Circuits of AES with a Low-depth Linear Layer and a New Structure
Haotian Shi, Xiutao Feng
Secret-key cryptography
In recent years quantum computing has developed rapidly. The security threat posed by quantum computing to cryptography makes it necessary to better evaluate the resource cost of attacking algorithms, some of which require quantum implementations of the attacked cryptographic building blocks. In this paper we manage to optimize quantum circuits of AES in several aspects. Firstly, based on de Brugière \textit{et al.}'s greedy algorithm, we propose an improved depth-oriented algorithm for...
Efficient and Generic Methods to Achieve Active Security in Private Information Retrieval and More Advanced Database Search
Reo Eriguchi, Kaoru Kurosawa, Koji Nuida
Cryptographic protocols
Motivated by secure database search, we present secure computation protocols for a function $f$ in the client-servers setting, where a client can obtain $f(x)$ on a private input $x$ by communicating with multiple servers each holding $f$. Specifically, we propose generic compilers from passively secure protocols, which only keep security against servers following the protocols, to actively secure protocols, which guarantee privacy and correctness even against malicious servers. Our...
Universal Composable Password Authenticated Key Exchange for the Post-Quantum World
You Lyu, Shengli Liu, Shuai Han
Cryptographic protocols
In this paper, we construct the first password authenticated key exchange (PAKE) scheme from isogenies with Universal Composable (UC) security in the random oracle model (ROM). We also construct the first two PAKE schemes with UC security in the quantum random oracle model (QROM), one is based on the learning with error (LWE) assumption, and the other is based on the group-action decisional Diffie- Hellman (GA-DDH) assumption in the isogeny setting.
To obtain our UC-secure PAKE scheme in...
Preimage Attacks on Reduced-Round Ascon-Xof
Seungjun Baek, Giyoon Kim, Jongsung Kim
Attacks and cryptanalysis
Ascon, a family of algorithms that supports authenticated encryption and hashing, has been selected as the new standard for lightweight cryptography in the NIST Lightweight Cryptography Project. Ascon’s permutation and authenticated encryption have been actively analyzed, but there are relatively few analyses on the hashing. In this paper, we concentrate on preimage attacks on Ascon-Xof. We focus on linearizing the polynomials leaked by the hash value to find its inverse. In an attack on...
Key Recovery Attack on the Partial Vandermonde Knapsack Problem
Dipayan Das, Antoine Joux
Attacks and cryptanalysis
The Partial Vandermonde (PV) Knapsack problem is an algebraic variant of the low-density inhomogeneous SIS problem. The problem has been used as a building block for various lattice-based constructions, including signatures (ACNS'14, ACISP'18), encryptions (DCC'15,DCC'20), and signature aggregation (Eprint'20). At Crypto'22, Boudgoust, Gachon, and Pellet-Mary proposed a key distinguishing attack on the PV Knapsack exploiting algebraic properties of the problem. Unfortunately, their attack...
Integrating Causality in Messaging Channels
Shan Chen, Marc Fischlin
Cryptographic protocols
Causal reasoning plays an important role in the comprehension of communication, but it has been elusive so far how causality should be properly preserved by instant messaging services. To the best of our knowledge, causality preservation is not even treated as a desired security property by most (if not all) existing secure messaging protocols like Signal. This is probably due to the intuition that causality seems already preserved when all received messages are intact and displayed...
Key-Recovery Attack on a Public-Key Encryption Related to Planted Clique
Caicai Chen, Chris Jones
Public-key cryptography
Hudoba proposed a public key encryption (PKE) scheme and conjectured its security to be based on the Planted Clique problem. In this note, we show that this scheme is not secure. We do so by devising an efficient algorithm for the even neighbor independent set problem proposed by Hudoba. This leaves open the possibility of building PKE based on Planted Clique.
Security analysis of the iMessage PQ3 protocol
Douglas Stebila
Cryptographic protocols
The iMessage PQ3 protocol is an end-to-end encrypted messaging protocol designed for exchanging data in long-lived sessions between two devices. It aims to provide classical and post-quantum confidentiality for forward secrecy and post-compromise secrecy, as well as classical authentication. Its initial authenticated key exchange is constructed from digital signatures plus elliptic curve Diffie–Hellman and post-quantum key exchanges; to derive per-message keys on an ongoing basis, it employs...
Adaptively Secure Streaming Functional Encryption
Pratish Datta, Jiaxin Guan, Alexis Korb, Amit Sahai
Cryptographic protocols
This paper introduces the first adaptively secure streaming functional encryption (sFE) scheme for P/Poly. sFE stands as an evolved variant of traditional functional encryption (FE), catering specifically to contexts with vast and/or dynamically evolving data sets. sFE is designed for applications where data arrives in a streaming fashion and is computed on in an iterative manner as the stream arrives. Unlike standard FE, in sFE: (1) encryption is possible without knowledge of the full data...
A Computational Tsirelson's Theorem for the Value of Compiled XOR Games
David Cui, Giulio Malavolta, Arthur Mehta, Anand Natarajan, Connor Paddock, Simon Schmidt, Michael Walter, Tina Zhang
Nonlocal games are a foundational tool for understanding entanglement and constructing quantum protocols in settings with multiple spatially separated quantum devices. In this work, we continue the study initiated by Kalai et al. (STOC '23) of compiled nonlocal games, played between a classical verifier and a single cryptographically limited quantum device. Our main result is that the compiler proposed by Kalai et al. is sound for any two-player XOR game. A celebrated theorem of Tsirelson...
A data aggregation protocol based on TFHE
Maria Ferrara, Antonio Tortora, Maria Tota
Cryptographic protocols
Torus Fully Homomorphic Encryption (TFHE) is a probabilistic cryptosytem over the real torus which allows one to operate directly on encrypted data without first decrypting them. We present an aggregation protocol based on a variant of TFHE for computing the sum of sensitive data, working only with the corresponding ciphertexts. Our scheme is an ideal choice for a system of smart meters - electronic devices for measuring energy consumption - that demands consumers’
privacy. In contrast to...
An Efficient Adaptive Attack Against FESTA
Guoqing Zhou, Maozhi Xu
Attacks and cryptanalysis
At EUROCRYPT’23, Castryck and Decru, Maino et al., and Robert present efficient attacks against supersingular isogeny Diffie-Hellman key exchange protocol (SIDH). Drawing inspiration from these attacks, Andrea Basso, Luciano Maino, and Giacomo Pope introduce FESTA, an isogeny-based trapdoor function, along with a corresponding IND-CCA secure public key encryption (PKE) protocol at ASIACRYPT’23. FESTA incorporates either a diagonal or circulant matrix into the secret key to mask torsion...
2024/343
Last updated: 2024-04-08
Partial Differential Fault Analysis on Ascon
Yang Gao
Attacks and cryptanalysis
Authenticated Encryption with Associated Data (AEAD) is a trend in applied cryptography because it combine confidentiality, integrity, and authentication into one algorithm and is more efficient than using block ciphers and hash functions separately. The Ascon algorithm, as the winner in both the CAESAR competition and the NIST LwC competition, will soon become the AEAD standard for protecting the Internet of Things and micro devices with limited computing resources. We propose a partial...
A New Approach for Non-Interactive Zero-Knowledge from Learning with Errors
Brent Waters
Foundations
We put forward a new approach for achieving non-interactive zero-knowledge proofs (NIKZs) from the learning with errors (LWE) assumption (with subexponential modulus to noise ratio). We provide a LWE-based construction of a hidden bits generator that gives rise to a NIZK via the celebrated hidden bits paradigm. A noteable feature of our construction is its simplicity. Our construction employs lattice trapdoors, but beyond that uses only simple operations. Unlike prior solutions we do not...
Fuzzy Private Set Intersection with Large Hyperballs
Aron van Baarsen, Sihang Pu
Cryptographic protocols
Traditional private set intersection (PSI) involves a receiver and a sender holding sets $X$ and $Y$, respectively, with the receiver learning only the intersection $X\cap Y$.
We turn our attention to its fuzzy variant, where the receiver holds \(|X|\) hyperballs of radius \(\delta\) in a metric space and the sender has $|Y|$ points.
Representing the hyperballs by their center, the receiver learns the points $x\in X$ for which there exists $y\in Y$ such that $\mathsf{dist}(x,y)\leq...
Attribute-Based Signatures with Advanced Delegation, and Tracing
Cécile Delerablée, Lénaïck Gouriou, David Pointcheval
Public-key cryptography
Attribute-based cryptography allows fine-grained control on the use of the private key. In particular, attribute-based signature (ABS) specifies the capabilities of the signer, which can only sign messages associated to a policy that is authorized by his set of attributes. Furthermore, we can expect signature to not leak any information about the identity of the signer. ABS is a useful tool for identity-preserving authentication process which requires granular access-control, and can...
Registered Functional Encryptions from Pairings
Ziqi Zhu, Jiangtao Li, Kai Zhang, Junqing Gong, Haifeng Qian
Public-key cryptography
This work initiates the study of concrete registered functional encryption (Reg-FE) beyond ``all-or-nothing'' functionalities:
- We build the first Reg-FE for linear function or inner-product evaluation (Reg-IPFE) from pairings. The scheme achieves adaptive IND-security under $k$-Lin assumption in the prime-order bilinear group. A minor modification yields the first Registered Inner-Product Encryption (Reg-IPE) scheme from $k$-Lin assumption. Prior work achieves the same security in...
Under What Conditions Is Encrypted Key Exchange Actually Secure?
Jake Januzelli, Lawrence Roy, Jiayu Xu
Cryptographic protocols
A Password-Authenticated Key Exchange (PAKE) protocol allows two parties to agree upon a cryptographic key, in the setting where the only secret shared in advance is a low-entropy password. The standard security notion for PAKE is in the Universal Composability (UC) framework. In recent years there have been a large number of works analyzing the UC-security of Encrypted Key Exchange (EKE), the very first PAKE protocol, and its One-encryption variant (OEKE), both of which compile an...
Theoretical Explanation and Improvement of Deep Learning-aided Cryptanalysis
Weixi Zheng, Liu Zhang, Zilong Wang
Attacks and cryptanalysis
At CRYPTO 2019, Gohr demonstrated that differential-neural distinguishers (DNDs) for Speck32/64 can learn more features than classical cryptanalysis's differential distribution tables (DDT). Furthermore, a non-classical key recovery procedure is devised by combining the Upper Confidence Bound (UCB) strategy and the BayesianKeySearch algorithm. Consequently, the time complexity of 11-round key recovery attacks on Speck32/64 is significantly reduced compared with the state-of-the-art results...
On the cryptosystems based on two Eulerian transfor-mations defined over the commutative rings $Z_{2^s}, s>1$.
Vasyl Ustimenko
Cryptographic protocols
We suggest the family of ciphers s^E^n, n=2,3,.... with the space of plaintexts (Z*_{2^s})^n, s >1 such that the encryption map is the composition of kind G=G_1A_1G_2A_2 where A_i are the affine transformations from AGL_n(Z_{2^s}) preserving the variety (Z*_{2^s)}^n , Eulerian endomorphism G_i , i=1,2 of K[x_1, x_2,...., x_n] moves x_i to monomial term ϻ(x_1)^{d(1)}(x_2)^{d(2)}...(x_n)^{d(n)} , ϻϵ Z*_{2^s} and act on (Z*_{2^s})^n as bijective transformations.
The cipher is...
Exploring the Advantages and Challenges of Fermat NTT in FHE Acceleration
Andrey Kim, Ahmet Can Mert, Anisha Mukherjee, Aikata Aikata, Maxim Deryabin, Sunmin Kwon, HyungChul Kang, Sujoy Sinha Roy
Implementation
Recognizing the importance of fast and resource-efficient polynomial multiplication in homomorphic encryption, in this paper, we introduce a novel method that enables integer multiplier-less Number Theoretic Transform (NTT) for computing polynomial multiplication. First, we use a Fermat number as an auxiliary modulus of NTT. However, this approach of using Fermat number scales poorly with the degree of polynomial. Hence, we propose a transformation of a large-degree univariate polynomial...
SweetPAKE: Key exchange with decoy passwords
Afonso Arriaga, Peter Y.A. Ryan, Marjan Skrobot
Cryptographic protocols
Decoy accounts are often used as an indicator of the compromise of sensitive data, such as password files. An attacker targeting only specific known-to-be-real accounts might, however, remain undetected. A more effective method proposed by Juels and Rivest at CCS'13 is to maintain additional fake passwords associated with each account. An attacker who gains access to the password file is unable to tell apart real passwords from fake passwords, and the attempted usage of a false password...
Diving Deep into the Preimage Security of AES-like Hashing
Shiyao Chen, Jian Guo, Eik List, Danping Shi, Tianyu Zhang
Attacks and cryptanalysis
Since the seminal works by Sasaki and Aoki, Meet-in-the-Middle (MITM) attacks are recognized as an effective technique for preimage and collision attacks on hash functions. At Eurocrypt 2021, Bao et al. automated MITM attacks on AES-like hashing and improved upon the best manual result. The attack framework has been furnished by subsequent works, yet far from complete. This paper elucidates three key contributions dedicated in further generalizing the idea of MITM and refining the automatic...
Accelerating Training and Enhancing Security Through Message Size Optimization in Symmetric Cryptography
ABHISAR, Madhav Yadav, Girish Mishra
This research extends Abadi and Andersen's exploration of neural networks using secret keys for information protection in multiagent systems. Focusing on enhancing confidentiality properties, we employ end-to-end adversarial training with neural networks Alice, Bob, and Eve. Unlike prior work limited to 64-bit messages, our study spans message sizes from 4 to 1024 bits, varying batch sizes and training steps. An innovative aspect involves training model Bob to approach a minimal error value...
Multiplex: TBC-based Authenticated Encryption with Sponge-Like Rate
Thomas Peters, Yaobin Shen, François-Xavier Standaert
Secret-key cryptography
Authenticated Encryption (AE) modes of operation based on Tweakable Block Ciphers (TBC) usually measure efficiency in the number of calls to the underlying primitive per message block. On the one hand, many existing solutions reach a primitive-rate of 1, meaning that each n-bit block of message asymptotically needs a single call to the TBC with output length n. On the other hand, while these modes look optimal in a blackbox setting, they become less attractive when leakage comes into play,...
Registered Attribute-Based Signature
Yijian Zhang, Jun Zhao, Ziqi Zhu, Junqing Gong, Jie Chen
Public-key cryptography
This paper introduces the notion of registered attribute-based signature (registered ABS). Distinctly different from classical attribute-based signature (ABS), registered ABS allows any user to generate their own public/secret key pair and register it with the system. The key curator is critical to keep the system flowing, which is a fully transparent entity that does not retain secrets. Our results can be summarized as follows.
-This paper provides the first definition of registered...
IDEA-DAC: Integrity-Driven Editing for Accountable Decentralized Anonymous Credentials via ZK-JSON
Shuhao Zheng, Zonglun Li, Junliang Luo, Ziyue Xin, Xue Liu
Applications
Decentralized Anonymous Credential (DAC) systems are increasingly relevant, especially when enhancing revocation mechanisms in the face of complex traceability challenges. This paper introduces IDEA-DAC, a paradigm shift from the conventional revoke-and-reissue methods, promoting direct and Integrity-Driven Editing (IDE) for Accountable DACs, which results in better integrity accountability, traceability, and system simplicity. We further incorporate an Edit-bound Conformity Check that...
Practical Improvements to Statistical Ineffective Fault Attacks
Barış Ege, Bob Swinkels, Dilara Toprakhisar, Praveen Kumar Vadnala
Attacks and cryptanalysis
Statistical Fault Attacks (SFA), introduced by Fuhr et al., exploit the statistical bias resulting from injected faults. Unlike prior fault analysis attacks, which require both faulty and correct ciphertexts under the same key, SFA leverages only faulty ciphertexts. In CHES 2018, more powerful attacks called Statistical Ineffective Fault Attacks (SIFA) have been proposed. In contrast to the previous fault attacks that utilize faulty ciphertexts, SIFA exploits the distribution of the...
Amortized Large Look-up Table Evaluation with Multivariate Polynomials for Homomorphic Encryption
Heewon Chung, Hyojun Kim, Young-Sik Kim, Yongwoo Lee
Applications
We present a new method for efficient look-up table (LUT) evaluation in homomorphic encryption (HE), based on Ring-LWE-based HE schemes, including both integer-message schemes such as Brakerski-Gentry-Vaikuntanathan (BGV) and Brakerski/Fan-Vercauteren (BFV), and complex-number-message schemes like the Cheon-Kim-Kim-Song (CKKS) scheme. Our approach encodes bit streams into codewords and translates LUTs into low-degree multivariate polynomials, allowing for the simultaneous evaluation of...
Information-Theoretic Homomorphic Encryption and 2-Party Computation
Jonathan Trostle
Cryptographic protocols
Homomorphic encryption has been an active area of research since Gentry's breakthrough results on fully homomorphic encryption.
We present secret key somewhat homomorphic schemes where client privacy is information-theoretic (server can be computationally unbounded). As the group order in our schemes gets larger, entropy approaches max-
imal entropy (perfect security). Our basic scheme is additive somewhat homomorphic. In one scheme, the server handles circuit multiplication gates by...
Deep Learning Based Analysis of Key Scheduling Algorithm of Advanced Ciphers
Narendra Kumar Patel, Hemraj Shobharam Lamkuche
Attacks and cryptanalysis
The advancements in information technology have made the Advanced Encryption Standard (AES) and the PRESENT cipher indispensable in ensuring data security and facilitating private transactions. AES is renowned for its flexibility and widespread use in various fields, while the PRESENT cipher excels in lightweight cryptographic situations. This paper delves into a dual examination of the Key Scheduling Algorithms (KSAs) of AES and the PRESENT cipher, which play a crucial role in generating...
WhisPIR: Stateless Private Information Retrieval with Low Communication
Leo de Castro, Kevin Lewi, Edward Suh
Recent constructions of private information retrieval (PIR) have seen significant improvements in computational performance. However, these improvements rely on heavy offline preprocessing that is typically difficult in real-world applications. Motivated by the question of PIR with no offline processing, we introduce WhisPIR, a fully stateless PIR protocol with low per-query communication. WhisPIR clients are all ephemeral, meaning that they appear with only the protocol public parameters...
With the rising popularity of DeFi applications it is important to implement protections for regular users of these DeFi platforms against large parties with massive amounts of resources allowing them to engage in market manipulation strategies such as frontrunning/backrunning. Moreover, there are many situations (such as recovery of funds from vulnerable smart contracts) where a user may not want to reveal their transaction until it has been executed. As such, it is clear that preserving...
To introduce a post-quantum-secure encryption scheme specifically for use in flight-computers, we used avionics’ module-isolation methods to wrap a recent encryption standard (HPKE – Hybrid Public Key Encryption) within a software partition. This solution proposes an upgrade to HPKE, using quantum-resistant ciphers (Kyber/ML-KEM and Dilithium/ML-DSA) redundantly alongside well-established ciphers, to achieve post-quantum security. Because cryptographic technology can suddenly become...
Certain applications such as FHE transciphering require randomness while operating over encrypted data. This randomness has to be obliviously generated in the encrypted domain and remain encrypted throughout the computation. Moreover, it should be guaranteed that independent-looking random coins can be obliviously generated for different computations. In this work, we consider the homomorphic evaluation of pseudorandom functions (PRFs) with a focus on practical lattice-based candidates....
Privacy-preserving decision tree evaluation (PDTE) allows a client that holds feature vectors to perform inferences against a decision tree model on the server side without revealing feature vectors to the server. Our work focuses on the non-interactive batched setting where the client sends a batch of encrypted feature vectors and then obtains classifications, without any additional interaction. This is useful in privacy-preserving credit scoring, biometric authentication, and many more...
Functional Encryption (FE) allows users to extract specific function-related information from encrypted data while preserving the privacy of the underlying plaintext. Though significant research has been devoted to developing secure and efficient Multi-Input Functional Encryption schemes supporting diverse functions, there remains a noticeable research gap in the development of verifiable FE schemes. Functionality and performance have received considerable attention, however, the crucial...
This paper introduces a novel protocol for privacy-preserving biometric identification, named Monchi, that combines the use of homomorphic encryption for the computation of the identification score with function secret sharing to obliviously compare this score with a given threshold and finally output the binary result. Given the cost of homomorphic encryption, BFV in this solution, we study and evaluate the integration of two packing solutions that enable the regrouping of multiple...
Machine learning (ML) as a service has emerged as a rapidly expanding field across various industries like healthcare, finance, marketing, retail and e-commerce, Industry 4.0, etc where a huge amount of data is gen- erated. To handle this amount of data, huge computational power is required for which cloud computing used to be the first choice. However, there are several challenges in cloud computing like limitations of bandwidth, network connectivity, higher latency, etc. To address...
This paper defines a post-quantum encryption scheme based on discussion cryptography by introducing a new post-quantum hard problem called Q-Problem. The idea behind this scheme is to hide the keys of each entity, and the encryption process is based on secret message holders using only random private keys.
Storage of sensitive multi-dimensional arrays must be secure and efficient in storage and processing time. Searchable encryption allows one to trade between security and efficiency. Searchable encryption design focuses on building indexes, overlooking the crucial aspect of record retrieval. Gui et al. (PoPETS 2023) showed that understanding the security and efficiency of record retrieval is critical to understand the overall system. A common technique for improving security is partitioning...
The NTRU problem has proven a useful building block for efficient bootstrapping in Fully Homomorphic Encryption (FHE) schemes, and different such schemes have been proposed. FINAL (ASIACRYPT 2022) first constructed FHE using homomorphic multiplexer (CMux) gates for the blind rotation operation. Later, XZD+23 (CRYPTO 2023) gave an asymptotic optimization by changing the ciphertext format to enable ring automorphism evaluations. In this work, we examine an adaptation to FINAL to evaluate CMux...
A Verifiable Random Function (VRF) can be evaluated on an input by a prover who holds a secret key, generating a pseudorandom output and a proof of output validity that can be verified using the corresponding public key. VRFs are a central building block of committee election mechanisms that sample parties to execute tasks in cryptographic protocols, e.g. generating blocks in a Proof-of-Stake (PoS) blockchain or executing a round of MPC protocols. We propose the notion, and a matching...
Existing oblivious systems offer robust security by concealing memory access patterns, but they encounter significant scalability and performance challenges. Recent efforts to enhance the practicality of these systems involve embedding oblivious computation, e.g., oblivious sorting and shuffling, within Trusted Execution Environments (TEEs). For instance, oblivious sort has been heavily utilized: in Oblix (S&P'18), when oblivious indexes are created and accessed; in Snoopy's high-throughput...
In recent years, quantum technology has been rapidly developed. As security analyses for symmetric ciphers continue to emerge, many require an evaluation of the resources needed for the quantum circuit implementation of the encryption algorithm. In this regard, we propose the quantum circuit decision problem, which requires us to determine whether there exists a quantum circuit for a given permutation f using M ancilla qubits and no more than K quantum gates within the circuit depth D....
Machine learning as a service requires the client to trust the server and provide its own private information to use this service. Usually, clients may worry that their private data is being collected by server without effective supervision, and the server also aims to ensure proper management of the user data to foster the advancement of its services. In this work, we focus on private decision tree evaluation (PDTE) which can alleviates such privacy concerns associated with classification...
Blind signatures enable a receiver to obtain signatures on messages of its choice without revealing any message to the signer. Round-optimal blind signatures are designed as a two-round interactive protocol between a signer and receiver. Coincidentally, the choice of message is not important in many applications, and is routinely set as a random (unstructured) message by a receiver. With the goal of designing more efficient blind signatures for such applications, Hanzlik (Eurocrypt '23)...
Fully Homomorphic Encryption (FHE) is a powerful Privacy-Enhancing Technology (PET) that enables computations on encrypted data without having access to the secret key. While FHE holds immense potential for enhancing data privacy and security, creating its practical applications is associated with many difficulties. A significant barrier is the absence of easy-to-use, standardized components that developers can utilize as foundational building blocks. Addressing this gap requires...
Robustness has emerged as an important criterion for authenticated encryption, alongside the requirements of confidentiality and integrity. We introduce a novel notion, denoted as IND-rCCA, to formalize the robustness of authenticated encryption from the perspective of decryption leakage. This notion is an augmentation of common notions defined for AEAD schemes by considering indistinguishability of potential leakage due to decryption failure, particularly in the presence of multiple checks...
A common strategy for constructing multivariate encryption schemes is to use a central map that is easy to invert over an extension field, along with a small number of modifications to thwart potential attacks. In this work we study the effectiveness of these modifications, by deriving estimates for the number of degree fall polynomials. After developing the necessary tools, we focus on encryption schemes using the $C^*$ and Dobbertin central maps, with the internal perturbation (ip), and...
Fully homomorphic encryption (FHE) allows for evaluating arbitrary functions over encrypted data. In Multi-party FHE applications, different parties encrypt their secret data and submit ciphertexts to a server, which, according to the application logic, performs homomorphic operations on them. For example, in a secret voting application, the tally is computed by summing up the ciphertexts encoding the votes. Valid encrypted votes are of the form $E(0)$ and $E(1)$. A malicious voter could...
In this paper we study the effect of using small prime numbers within the Okamoto-Uchiyama public key encryption scheme. We introduce two novel versions and prove their security. Then we show how to choose the system's parameters such that the security results hold. Moreover, we provide a practical comparison between the cryptographic algorithms we introduced and the original Okamoto-Uchiyama cryptosystem.
Transformer neural networks have gained significant traction since their introduction, becoming pivotal across diverse domains. Particularly in large language models like Claude and ChatGPT, the transformer architecture has demonstrated remarkable efficacy. This paper provides a concise overview of transformer neural networks and delves into their security considerations, focusing on covert channel attacks and their implications for the safety of large language models. We present a covert...
The Number Theoretic Transform (NTT) is a powerful mathematical tool that has become increasingly important in developing Post Quantum Cryptography (PQC) and Homomorphic Encryption (HE). Its ability to efficiently calculate polynomial multiplication using the convolution theorem with a quasi-linear complexity $O(n \log{n})$ instead of $O(n^2)$ when implemented with Fast Fourier Transform-style algorithms has made it a key component in modern cryptography. FFT-style NTT algorithm or fast-NTT...
Dynamic Decentralized Functional Encryption (DDFE), introduced by Chotard et al. (CRYPTO'20), stands as a robust generalization of (Multi-Client) Functional Encryption. It enables users to dynamically join and contribute private inputs to individually-controlled joint functions, all without requiring a trusted authority. Agrawal et al. (TCC’21) further extended this line of research by presenting the first DDFE construction for function-hiding inner products (FH-IP-DDFE) in the random oracle...
Searchable Symmetric Encryption (SSE) has opened up an attractive avenue for privacy-preserved processing of outsourced data on the untrusted cloud infrastructure. SSE aims to support efficient Boolean query processing with optimal storage and search overhead over large real databases. However, current constructions in the literature lack the support for multi-client search and dynamic updates to the encrypted databases, which are essential requirements for the widespread deployment of SSE...
In this short note we review the technique proposed at ToSC 2018 by Sadeghi et al. for attacks built upon several related-tweakey impossible differential trails. We show that the initial encryption queries are improper and lead the authors to misevaluating a filtering value in the key recovery phase. We identified 4 papers (from Eurocrypt, DCC, ToSC and ePrint) that follow on the results of Sadeghi et al., and in three of them the issue was propagated. We thus present a careful analysis of...
Running machine learning algorithms on encrypted data is a way forward to marry functionality needs common in industry with the important concerns for privacy when working with potentially sensitive data. While there is already a growing field on this topic and a variety of protocols, mostly employing fully homomorphic encryption or performing secure multiparty computation (MPC), we are the first to propose a protocol that makes use of a specialized encryption scheme that allows to do secure...
Fully Homomorphic Encryption (FHE) is a powerful tool that brings privacy and security to all sorts of applications by allowing us to perform additions and multiplications directly on ciphertexts without the need of the secret key. Some applications of FHE that were previously overlooked but have recently been gaining traction are data compression and image processing. Practically, FHE enables applications such as private satellite searching, private object recognition, or even encrypted...
Structured Encryption (StE) enables a client to securely store and query data stored on an untrusted server. Recent constructions of StE have moved beyond basic queries, and now support large subsets of SQL. However, the security of these constructions is poorly understood, and no systematic analysis has been performed. We address this by providing the first leakage-abuse attacks against StE for SQL schemes. Our attacks can be run by a passive adversary on a server with access to some...
MRAE security is an important goal for many AEAD applications where the nonce uniqueness cannot be maintained and security risks are significant. However, MRAE schemes can be quite expensive. Two of the SoTA MRAE-secure schemes; Deoxys-II and AES-GCM-SIV rely on internal parallelism and special instructions to achieve competitive performance. However, they both suffer from the same bottleneck, they have at least one call to the underlying primitive that cannot be parallelized to any other...
FUTURE is a recently proposed lightweight block cipher that achieved a remarkable hardware performance due to careful design decisions. FUTURE is an Advanced Encryption Standard (AES)-like Substitution-Permutation Network (SPN) with 10 rounds, whose round function consists of four components, i.e., SubCell, MixColumn, ShiftRow and AddRoundKey. Unlike AES, it is a 64-bit-size block cipher with a 128-bit secret key, and the state can be arranged into 16 cells. Therefore, the operations of...
Nextcloud is a leading cloud storage platform with more than 20 million users. Nextcloud offers an end-to-end encryption (E2EE) feature that is claimed to be able “to keep extremely sensitive data fully secure even in case of a full server breach”. They also claim that the Nextcloud server “has Zero Knowledge, that is, never has access to any of the data or keys in unencrypted form”. This is achieved by having encryption and decryption operations that are done using file keys that are...
This paper introduces a new method for training decision trees and random forests using CKKS homomorphic encryption (HE) in cloud environments, enhancing data privacy from multiple sources. The innovative Homomorphic Binary Decision Tree (HBDT) method utilizes a modified Gini Impurity index (MGI) for node splitting in encrypted data scenarios. Notably, the proposed training approach operates in a single cloud security domain without the need for decryption, addressing key challenges in...
In this paper, we propose a novel isogeny-based public key encryption (PKE) scheme named LIT-SiGamal. This is based on a LIT diagram and SiGamal. SiGamal is an isogeny-based PKE scheme that uses a commutative diagram with an auxiliary point. LIT-SiGamal uses a LIT diagram which is a commutative diagram consisting of large-degree horizontal isogenies and relatively small-degree vertical isogenies, while the original SiGamal uses a CSIDH diagram. A strength of LIT-SiGamal is efficient...
Searchable symmetric encryption (SSE) schemes provide users with the ability to perform keyword searches on encrypted databases without the need for decryption. While this functionality is advantageous, it introduces the potential for inadvertent information disclosure, thereby exposing SSE systems to various types of attacks. In this work, we introduce a new inference attack aimed at enhancing the query recovery accuracy of RefScore (presented at USENIX 2021). The proposed approach...
Searchable symmetric encryption has been vulnerable to inference attacks that rely on uniqueness in leakage patterns. However, many keywords in datasets lack distinctive leakage patterns, limiting the effectiveness of such attacks. The file injection attacks, initially proposed by Cash et al. (CCS 2015), have shown impressive performance with 100% accuracy and no prior knowledge requirement. Nevertheless, this attack fails to recover queries with underlying keywords not present in the...
Quantum computers have the potential to solve hard problems that are nearly impossible to solve by classical computers, this has sparked a surge of research to apply quantum technology and algorithm against the cryptographic systems to evaluate for its quantum resistance. In the process of selecting post-quantum standards, NIST categorizes security levels based on the complexity that quantum computers would require to crack AES encryption (levels 1, 3 and 5) and SHA-2 or SHA-3 (levels 2 and...
We show how fixed-unitary quantum encryption schemes can be attacked in a black-box setting. We use an efficient technique to invert a unitary transformation on a quantum computer to retrieve an encrypted secret quantum state $\ket{\psi}$. This attack has a success rate of 100% and can be executed in constant time. We name a vulnerable scheme and suggest how to improve it to invalidate this attack. The proposed attack highlights the importance of carefully designing quantum encryption...
Oblivious message retrieval (OMR) allows messages resource-limited recipients to outsource the message retrieval process without revealing which messages are pertinent to which recipient. Its realizations in recent works leave an open problem: can an OMR scheme be both practical and provably secure against spamming attacks from malicious senders (i.e., DoS-resistant) under standard assumptions? In this paper, we first prove that a prior construction OMRp2 is DoS-resistant under a...
Nowadays Federated learning (FL) is established as one of the best techniques for collaborative machine learning. It allows a set of clients to train a common model without disclosing their sensitive and private dataset to a coordination server. The latter is in charge of the model aggregation. However, FL faces some problems, regarding the security of updates, integrity of computation and the availability of a server. In this paper, we combine some new ideas like clients’ reputation with...
Anonymous identity-based encryption (AIBE) is an extension of identity-based encryption (IBE) that enhances the privacy of a ciphertext by providing ciphertext anonymity. In this paper, we introduce the concept of revocable IBE with anonymous revocation (RIBE-AR), which is capable of issuing an update key and hiding the revoked set of the update key that efficiently revokes private keys of AIBE. We first define the security models of RIBE-AR and propose an efficient RIBE-AR scheme in...
Ciphertext-independent updatable encryption (UE) allows to rotate encryption keys and update ciphertexts via a token without the need to first download the ciphertexts. Although, syntactically, UE is a symmetric-key primitive, ciphertext-independent UE with forward secrecy and post-compromise security is known to imply public-key encryption (Alamati, Montgomery and Patranabis, CRYPTO 2019). Constructing post-quantum secure UE turns out to be a difficult task. While lattices offer the...
This paper introduces a high-performance and scalable hardware architecture designed for the Number-Theoretic Transform (NTT), a fundamental component extensively utilized in lattice-based encryption and fully homomorphic encryption schemes. The underlying rationale behind this research is to harness the advantages of the hypercube topology. This topology serves to significantly diminish the volume of data exchanges required during each iteration of the NTT, reducing it to a complexity of...
The income of companies working on data markets steadily grows year by year. Private function evaluation (PFE) is a valuable tool in solving corresponding security problems. The task of Controlled Private Function Evaluation and its relaxed version was introduced in [Horvath et.al., 2019]. In this article, we propose and examine several different approaches for such tasks with computational and information theoretical security against static corruption adversary. The latter level of security...
Threshold signatures have recently seen a renewed interest due to applications in cryptocurrency while NIST has released a call for multi-party threshold schemes, with a deadline for submission expected for the first half of 2025. So far, all lattice-based threshold signatures requiring less than two-rounds are based on heavy tools such as (fully) homomorphic encryption (FHE) and homomorphic trapdoor commitments (HTDC). This is not unexpected considering that most efficient two-round...
Policy-compliant signatures (PCS) are a recently introduced primitive by Badertscher et al. [TCC 2021] in which a central authority distributes secret and public keys associated with sets of attributes (e.g., nationality, affiliation with a specific department, or age) to its users. The authority also enforces a policy determining which senders can sign messages for which receivers based on a joint check of their attributes. For example, senders and receivers must have the same nationality,...
Over the past ten years, the statistical properties of random functions have been particularly fruitful for generic attacks. Initially, these attacks targeted iterated hash constructions and their combiners, developing a wide array of methods based on internal collisions and on the average behavior of iterated random functions. More recently, Gilbert et al. (EUROCRYPT 2023) introduced a forgery attack on so-called duplex-based Authenticated Encryption modes which was based on exceptional...
The elegant paradigm of Anamorphic Encryption (Persiano et al., Eurocrypt 2022) considers the question of establishing a private communication in a world controlled by a dictator. The challenge is to allow two users, sharing some secret anamorphic key, to exchange covert messages without the dictator noticing, even when the latter has full access to the regular secret keys. Over the last year several works considered this question and proposed constructions, novel extensions and...
The Advanced Encryption Standard (AES) is one of the most commonly used and analyzed encryption algorithms. In this work, we present new combinations of some prominent attacks on AES, achieving new records in data requirements among attacks, utilizing only $2^4$ and $2^{16}$ chosen plaintexts (CP) for 6-round and 7-round AES-192/256 respectively. One of our attacks is a combination of a meet-in-the-middle (MiTM) attack with a square attack mounted on 6-round AES-192/256 while ...
Secure multi-party computation aims to allow a set of players to compute a given function on their secret inputs without revealing any other information than the result of the computation. In this work, we focus on the design of secure multi-party protocols for shared polynomial operations. We consider the classical model where the adversary is honest-but-curious, and where the coefficients (or any secret values) are either encrypted using an additively homomorphic encryption scheme or...
This paper gives the first lattice-based two-round threshold signature based on lattice assumptions for which the first message is independent of the message being signed without relying on fully-homomorphic encryption, and our construction supports arbitrary thresholds. Our construction provides a careful instantiation of a generic threshold signature construction by Tessaro and Zhu (EUROCRYPT ’23) based on specific linear hash functions, which in turns can be seen as a generalization of...
Fully Homomorphic Encryption (FHE) is a cryptographic primitive that allows performing arbitrary operations on encrypted data. Since the conception of the idea in [RAD78], it was considered a holy grail of cryptography. After the first construction in 2009 [Gen09], it has evolved to become a practical primitive with strong security guarantees. Most modern constructions are based on well-known lattice problems such as Learning with Errors (LWE). Besides its academic appeal, in recent years...
Classifying images has become a straightforward and accessible task, thanks to the advent of Deep Neural Networks. Nevertheless, not much attention is given to the privacy concerns associated with sensitive data contained in images. In this study, we propose a solution to this issue by exploring an intersection between Machine Learning and cryptography. In particular, Fully Homomorphic Encryption (FHE) emerges as a promising solution, as it enables computations to be performed on encrypted...
Lattice-based cryptography has emerged as a promising new candidate to build cryptographic primitives. It offers resilience against quantum attacks, enables fully homomorphic encryption, and relies on robust theoretical foundations. Zero-knowledge proofs (ZKPs) are an essential primitive for various privacy-preserving applications. For example, anonymous credentials, group signatures, and verifiable oblivious pseudorandom functions all require ZKPs. Currently, the majority of ZKP systems are...
An Oblivious Pseudo-Random Function (OPRF) is a two-party protocol for jointly evaluating a Pseudo-Random Function (PRF), where a user has an input x and a server has an input k. At the end of the protocol, the user learns the evaluation of the PRF using key k at the value x, while the server learns nothing about the user's input or output. OPRFs are a prime tool for building secure authentication and key exchange from passwords, private set intersection, private information retrieval,...
Transport Layer Security ( TLS ) is foundational for safeguarding client-server communication. However, it does not extend integrity guarantees to third-party verification of data authenticity. If a client wants to present data obtained from a server, it cannot convince any other party that the data has not been tampered with. TLS oracles ensure data authenticity beyond the client-server TLS connection, such that clients can obtain data from a server and ensure provenance to any third...
Sparse binary LWE secrets are under consideration for standardization for Homomorphic Encryption and its applications to private computation. Known attacks on sparse binary LWE secrets include the sparse dual attack and the hybrid sparse dual-meet in the middle attack, which requires significant memory. In this paper, we provide a new statistical attack with low memory requirement. The attack relies on some initial parallelized lattice reduction. The key observation is that, after...
In the rapidly evolving fields of encryption and blockchain technologies, the efficiency and security of cryptographic schemes significantly impact performance. This paper introduces a comprehensive framework for continuous benchmarking in one of the most popular cryptography Rust libraries, fastcrypto. What makes our analysis unique is the realization that automated benchmarking is not just a performance monitor and optimization tool, but it can be used for cryptanalysis and innovation...
Order-Revealing Encryption (ORE) provides a practical solution for conducting range queries over encrypted data. Achieving a desirable privacy-efficiency tradeoff in designing ORE schemes has posed a significant challenge. At Asiacrypt 2018, Cash et al. proposed Parameter-hiding ORE (pORE), which specifically targets scenarios where the data distribution shape is known, but the underlying parameters (such as mean and variance) need to be protected. However, existing pORE constructions rely...
Approximate fully homomorphic encryption (FHE) schemes such as the CKKS scheme (Asiacrypt '17) are popular in practice due to their efficiency and utility for machine learning applications. Unfortunately, Li and Micciancio (Eurocrypt, '21) showed that, while achieving standard semantic (or $\mathsf{IND}\mbox{-}\mathsf{CPA}$ security), the CKKS scheme is broken under a variant security notion known as $\mathsf{IND}\mbox{-}\mathsf{CPA}^D$. Subsequently, Li, Micciancio, Schultz, and Sorrell...
We introduce a blockchain Fair Data Exchange (FDE) protocol, enabling a storage server to transfer a data file to a client atomically: the client receives the file if and only if the server receives an agreed-upon payment. We put forth a new definition for a cryptographic scheme that we name verifiable encryption under committed key (VECK), and we propose two instantiations for this scheme. Our protocol relies on a blockchain to enforce the atomicity of the exchange and uses VECK to ensure...
Fully homomorphic encryption (FHE) has attracted much attention recently. Chinese remainder representation (CRR) or RNS representation is one of the core technologies of FHE. CRR basis conversion is a key step of KeySwitching procedure. Bajard et al. proposed a fast basis conversion method for CRR basis conversion, but the elimination of error had to be ignored. Halevi et al. suggested a method using floating-point arithmetic to avoid errors, but floating-point arithmetic has its own issues...
The DECT Standard Cipher (DSC) is a proprietary stream cipher used for encryption in the Digital Enhanced Cordless Telecommunications (DECT), which is a standard for short range cordless communication and widely deployed worldwide both in residential and enterprise environments. New weaknesses of the DSC stream cipher which are not discovered in previous works are explored and analyzed in this paper. Based on these weaknesses, new practical key recovery attacks and distinguishing attack on...
Multiparty private set intersection (mPSI) protocol is capable of finding the intersection of multiple sets securely without revealing any other information. However, its limitation lies in processing only those elements present in every participant's set, which proves inadequate in scenarios where certain elements are common to several, but not all, sets. In this paper, we introduce an innovative variant of the mPSI protocol named unbalanced quorum PSI to fill in the gaps of the mPSI...
We present a new post-quantum Public Key Encryption scheme (PKE) named Supersingular Isogeny Lollipop Based Encryption or SILBE. SILBE is obtained by leveraging the generalized lollipop attack of Castryck and Vercauteren on the M-SIDH Key exchange by Fouotsa, Moriya and Petit. Doing so, we can in fact make of SILBE a post-quantum secure Updatable Public Key Encryption scheme (UPKE). SILBE is the first isogeny-based UPKE which is not based on group actions. In its core, SILBE extensively...
Verifiable random functions (VRFs) are pseudorandom functions with the addition that the function owner can prove that a generated output is correct, with respect to a committed key. In this paper we introduce the notion of an exponent-VRF, or eVRF, which is a VRF that does not provide its output $y$ explicitly, but instead provides $Y = y \cdot G$, where $G$ is a generator of some finite cyclic group (or $Y = g^y$ in multiplicative notation). We construct eVRFs from DDH and from the...
Confidentiality and authentication are two main security goals in secure electronic mail (e-mail). Furthermore, deniability is also a significant security property for some e-mail applications to protect the privacy of the sender. Although searchable encryption solves the keyword searching problem in a secure e-mail system, it also breaks the deniability of the system. Because the adversary can obtain the information of the data sender and data user from the trapdoor as well as ciphertext...
In this work, we present two generic frameworks for leakage-resilient attribute-based encryption (ABE), which is an improved version of ABE that can be proven secure even when part of the secret key is leaked. Our frameworks rely on the standard assumption ($k$-Lin) over prime-order groups. The first framework is designed for leakage-resilient ABE with attribute-hiding in the bounded leakage model. Prior to this work, no one had yet derived a generic leakage-resilient ABE framework with...
With the rapidly evolving landscape of cryptography, blockchain technology has advanced to cater to diverse user requirements, leading to the emergence of a multi-chain ecosystem featuring various use cases characterized by distinct transaction speed and decentralization trade-offs. At the heart of this evolution lies digital signature schemes, responsible for safeguarding blockchain-based assets such as ECDSA, Schnorr, and EdDSA, among others. However, a critical gap exists in the...
In recent years quantum computing has developed rapidly. The security threat posed by quantum computing to cryptography makes it necessary to better evaluate the resource cost of attacking algorithms, some of which require quantum implementations of the attacked cryptographic building blocks. In this paper we manage to optimize quantum circuits of AES in several aspects. Firstly, based on de Brugière \textit{et al.}'s greedy algorithm, we propose an improved depth-oriented algorithm for...
Motivated by secure database search, we present secure computation protocols for a function $f$ in the client-servers setting, where a client can obtain $f(x)$ on a private input $x$ by communicating with multiple servers each holding $f$. Specifically, we propose generic compilers from passively secure protocols, which only keep security against servers following the protocols, to actively secure protocols, which guarantee privacy and correctness even against malicious servers. Our...
In this paper, we construct the first password authenticated key exchange (PAKE) scheme from isogenies with Universal Composable (UC) security in the random oracle model (ROM). We also construct the first two PAKE schemes with UC security in the quantum random oracle model (QROM), one is based on the learning with error (LWE) assumption, and the other is based on the group-action decisional Diffie- Hellman (GA-DDH) assumption in the isogeny setting. To obtain our UC-secure PAKE scheme in...
Ascon, a family of algorithms that supports authenticated encryption and hashing, has been selected as the new standard for lightweight cryptography in the NIST Lightweight Cryptography Project. Ascon’s permutation and authenticated encryption have been actively analyzed, but there are relatively few analyses on the hashing. In this paper, we concentrate on preimage attacks on Ascon-Xof. We focus on linearizing the polynomials leaked by the hash value to find its inverse. In an attack on...
The Partial Vandermonde (PV) Knapsack problem is an algebraic variant of the low-density inhomogeneous SIS problem. The problem has been used as a building block for various lattice-based constructions, including signatures (ACNS'14, ACISP'18), encryptions (DCC'15,DCC'20), and signature aggregation (Eprint'20). At Crypto'22, Boudgoust, Gachon, and Pellet-Mary proposed a key distinguishing attack on the PV Knapsack exploiting algebraic properties of the problem. Unfortunately, their attack...
Causal reasoning plays an important role in the comprehension of communication, but it has been elusive so far how causality should be properly preserved by instant messaging services. To the best of our knowledge, causality preservation is not even treated as a desired security property by most (if not all) existing secure messaging protocols like Signal. This is probably due to the intuition that causality seems already preserved when all received messages are intact and displayed...
Hudoba proposed a public key encryption (PKE) scheme and conjectured its security to be based on the Planted Clique problem. In this note, we show that this scheme is not secure. We do so by devising an efficient algorithm for the even neighbor independent set problem proposed by Hudoba. This leaves open the possibility of building PKE based on Planted Clique.
The iMessage PQ3 protocol is an end-to-end encrypted messaging protocol designed for exchanging data in long-lived sessions between two devices. It aims to provide classical and post-quantum confidentiality for forward secrecy and post-compromise secrecy, as well as classical authentication. Its initial authenticated key exchange is constructed from digital signatures plus elliptic curve Diffie–Hellman and post-quantum key exchanges; to derive per-message keys on an ongoing basis, it employs...
This paper introduces the first adaptively secure streaming functional encryption (sFE) scheme for P/Poly. sFE stands as an evolved variant of traditional functional encryption (FE), catering specifically to contexts with vast and/or dynamically evolving data sets. sFE is designed for applications where data arrives in a streaming fashion and is computed on in an iterative manner as the stream arrives. Unlike standard FE, in sFE: (1) encryption is possible without knowledge of the full data...
Nonlocal games are a foundational tool for understanding entanglement and constructing quantum protocols in settings with multiple spatially separated quantum devices. In this work, we continue the study initiated by Kalai et al. (STOC '23) of compiled nonlocal games, played between a classical verifier and a single cryptographically limited quantum device. Our main result is that the compiler proposed by Kalai et al. is sound for any two-player XOR game. A celebrated theorem of Tsirelson...
Torus Fully Homomorphic Encryption (TFHE) is a probabilistic cryptosytem over the real torus which allows one to operate directly on encrypted data without first decrypting them. We present an aggregation protocol based on a variant of TFHE for computing the sum of sensitive data, working only with the corresponding ciphertexts. Our scheme is an ideal choice for a system of smart meters - electronic devices for measuring energy consumption - that demands consumers’ privacy. In contrast to...
At EUROCRYPT’23, Castryck and Decru, Maino et al., and Robert present efficient attacks against supersingular isogeny Diffie-Hellman key exchange protocol (SIDH). Drawing inspiration from these attacks, Andrea Basso, Luciano Maino, and Giacomo Pope introduce FESTA, an isogeny-based trapdoor function, along with a corresponding IND-CCA secure public key encryption (PKE) protocol at ASIACRYPT’23. FESTA incorporates either a diagonal or circulant matrix into the secret key to mask torsion...
Authenticated Encryption with Associated Data (AEAD) is a trend in applied cryptography because it combine confidentiality, integrity, and authentication into one algorithm and is more efficient than using block ciphers and hash functions separately. The Ascon algorithm, as the winner in both the CAESAR competition and the NIST LwC competition, will soon become the AEAD standard for protecting the Internet of Things and micro devices with limited computing resources. We propose a partial...
We put forward a new approach for achieving non-interactive zero-knowledge proofs (NIKZs) from the learning with errors (LWE) assumption (with subexponential modulus to noise ratio). We provide a LWE-based construction of a hidden bits generator that gives rise to a NIZK via the celebrated hidden bits paradigm. A noteable feature of our construction is its simplicity. Our construction employs lattice trapdoors, but beyond that uses only simple operations. Unlike prior solutions we do not...
Traditional private set intersection (PSI) involves a receiver and a sender holding sets $X$ and $Y$, respectively, with the receiver learning only the intersection $X\cap Y$. We turn our attention to its fuzzy variant, where the receiver holds \(|X|\) hyperballs of radius \(\delta\) in a metric space and the sender has $|Y|$ points. Representing the hyperballs by their center, the receiver learns the points $x\in X$ for which there exists $y\in Y$ such that $\mathsf{dist}(x,y)\leq...
Attribute-based cryptography allows fine-grained control on the use of the private key. In particular, attribute-based signature (ABS) specifies the capabilities of the signer, which can only sign messages associated to a policy that is authorized by his set of attributes. Furthermore, we can expect signature to not leak any information about the identity of the signer. ABS is a useful tool for identity-preserving authentication process which requires granular access-control, and can...
This work initiates the study of concrete registered functional encryption (Reg-FE) beyond ``all-or-nothing'' functionalities: - We build the first Reg-FE for linear function or inner-product evaluation (Reg-IPFE) from pairings. The scheme achieves adaptive IND-security under $k$-Lin assumption in the prime-order bilinear group. A minor modification yields the first Registered Inner-Product Encryption (Reg-IPE) scheme from $k$-Lin assumption. Prior work achieves the same security in...
A Password-Authenticated Key Exchange (PAKE) protocol allows two parties to agree upon a cryptographic key, in the setting where the only secret shared in advance is a low-entropy password. The standard security notion for PAKE is in the Universal Composability (UC) framework. In recent years there have been a large number of works analyzing the UC-security of Encrypted Key Exchange (EKE), the very first PAKE protocol, and its One-encryption variant (OEKE), both of which compile an...
At CRYPTO 2019, Gohr demonstrated that differential-neural distinguishers (DNDs) for Speck32/64 can learn more features than classical cryptanalysis's differential distribution tables (DDT). Furthermore, a non-classical key recovery procedure is devised by combining the Upper Confidence Bound (UCB) strategy and the BayesianKeySearch algorithm. Consequently, the time complexity of 11-round key recovery attacks on Speck32/64 is significantly reduced compared with the state-of-the-art results...
We suggest the family of ciphers s^E^n, n=2,3,.... with the space of plaintexts (Z*_{2^s})^n, s >1 such that the encryption map is the composition of kind G=G_1A_1G_2A_2 where A_i are the affine transformations from AGL_n(Z_{2^s}) preserving the variety (Z*_{2^s)}^n , Eulerian endomorphism G_i , i=1,2 of K[x_1, x_2,...., x_n] moves x_i to monomial term ϻ(x_1)^{d(1)}(x_2)^{d(2)}...(x_n)^{d(n)} , ϻϵ Z*_{2^s} and act on (Z*_{2^s})^n as bijective transformations. The cipher is...
Recognizing the importance of fast and resource-efficient polynomial multiplication in homomorphic encryption, in this paper, we introduce a novel method that enables integer multiplier-less Number Theoretic Transform (NTT) for computing polynomial multiplication. First, we use a Fermat number as an auxiliary modulus of NTT. However, this approach of using Fermat number scales poorly with the degree of polynomial. Hence, we propose a transformation of a large-degree univariate polynomial...
Decoy accounts are often used as an indicator of the compromise of sensitive data, such as password files. An attacker targeting only specific known-to-be-real accounts might, however, remain undetected. A more effective method proposed by Juels and Rivest at CCS'13 is to maintain additional fake passwords associated with each account. An attacker who gains access to the password file is unable to tell apart real passwords from fake passwords, and the attempted usage of a false password...
Since the seminal works by Sasaki and Aoki, Meet-in-the-Middle (MITM) attacks are recognized as an effective technique for preimage and collision attacks on hash functions. At Eurocrypt 2021, Bao et al. automated MITM attacks on AES-like hashing and improved upon the best manual result. The attack framework has been furnished by subsequent works, yet far from complete. This paper elucidates three key contributions dedicated in further generalizing the idea of MITM and refining the automatic...
This research extends Abadi and Andersen's exploration of neural networks using secret keys for information protection in multiagent systems. Focusing on enhancing confidentiality properties, we employ end-to-end adversarial training with neural networks Alice, Bob, and Eve. Unlike prior work limited to 64-bit messages, our study spans message sizes from 4 to 1024 bits, varying batch sizes and training steps. An innovative aspect involves training model Bob to approach a minimal error value...
Authenticated Encryption (AE) modes of operation based on Tweakable Block Ciphers (TBC) usually measure efficiency in the number of calls to the underlying primitive per message block. On the one hand, many existing solutions reach a primitive-rate of 1, meaning that each n-bit block of message asymptotically needs a single call to the TBC with output length n. On the other hand, while these modes look optimal in a blackbox setting, they become less attractive when leakage comes into play,...
This paper introduces the notion of registered attribute-based signature (registered ABS). Distinctly different from classical attribute-based signature (ABS), registered ABS allows any user to generate their own public/secret key pair and register it with the system. The key curator is critical to keep the system flowing, which is a fully transparent entity that does not retain secrets. Our results can be summarized as follows. -This paper provides the first definition of registered...
Decentralized Anonymous Credential (DAC) systems are increasingly relevant, especially when enhancing revocation mechanisms in the face of complex traceability challenges. This paper introduces IDEA-DAC, a paradigm shift from the conventional revoke-and-reissue methods, promoting direct and Integrity-Driven Editing (IDE) for Accountable DACs, which results in better integrity accountability, traceability, and system simplicity. We further incorporate an Edit-bound Conformity Check that...
Statistical Fault Attacks (SFA), introduced by Fuhr et al., exploit the statistical bias resulting from injected faults. Unlike prior fault analysis attacks, which require both faulty and correct ciphertexts under the same key, SFA leverages only faulty ciphertexts. In CHES 2018, more powerful attacks called Statistical Ineffective Fault Attacks (SIFA) have been proposed. In contrast to the previous fault attacks that utilize faulty ciphertexts, SIFA exploits the distribution of the...
We present a new method for efficient look-up table (LUT) evaluation in homomorphic encryption (HE), based on Ring-LWE-based HE schemes, including both integer-message schemes such as Brakerski-Gentry-Vaikuntanathan (BGV) and Brakerski/Fan-Vercauteren (BFV), and complex-number-message schemes like the Cheon-Kim-Kim-Song (CKKS) scheme. Our approach encodes bit streams into codewords and translates LUTs into low-degree multivariate polynomials, allowing for the simultaneous evaluation of...
Homomorphic encryption has been an active area of research since Gentry's breakthrough results on fully homomorphic encryption. We present secret key somewhat homomorphic schemes where client privacy is information-theoretic (server can be computationally unbounded). As the group order in our schemes gets larger, entropy approaches max- imal entropy (perfect security). Our basic scheme is additive somewhat homomorphic. In one scheme, the server handles circuit multiplication gates by...
The advancements in information technology have made the Advanced Encryption Standard (AES) and the PRESENT cipher indispensable in ensuring data security and facilitating private transactions. AES is renowned for its flexibility and widespread use in various fields, while the PRESENT cipher excels in lightweight cryptographic situations. This paper delves into a dual examination of the Key Scheduling Algorithms (KSAs) of AES and the PRESENT cipher, which play a crucial role in generating...
Recent constructions of private information retrieval (PIR) have seen significant improvements in computational performance. However, these improvements rely on heavy offline preprocessing that is typically difficult in real-world applications. Motivated by the question of PIR with no offline processing, we introduce WhisPIR, a fully stateless PIR protocol with low per-query communication. WhisPIR clients are all ephemeral, meaning that they appear with only the protocol public parameters...
