Dates are inconsistent

Dates are inconsistent

135 results sorted by ID

2025/1199 (PDF) Last updated: 2025-06-27
HypSCA: A Hyperbolic Embedding Method for Enhanced Side-channel Attack
Kaibin Li, Yihuai Liang, Zhengchun Zhou, Shui Yu
Attacks and cryptanalysis

Deep learning-based side-channel attack (DLSCA) has become the dominant paradigm for extracting sensitive information from hardware implementations due to its ability to learn discriminative features directly from raw side-channel traces. A common design choice in DLSCA involves embedding traces in Euclidean space, where the underlying geometry supports conventional objectives such as classification or contrastive learning. However, Euclidean space is fundamentally limited in capturing the...

2025/1176 (PDF) Last updated: 2025-07-06
Solve Approximate CVP via Variants of Nearest-Colattice
Wenwen Xia, Geng Wang, Dawu Gu
Attacks and cryptanalysis

The approximate Closest Vector Problem (CVP) is a core computational problem underlying many post-quantum lattice-based signature schemes, including Dilithium, one-more-ISIS, and HuFu. While the security of these schemes is typically expressed in terms of the Inhomogeneous Short Integer Solution (ISIS) problem, it is well-known that ISIS can be efficiently reduced to approximate CVP. Despite its foundational role, approximate CVP with non-negligible approximation factors remains far less...

2025/1115 (PDF) Last updated: 2025-06-13
High-Throughput Permissionless Blockchain Consensus under Realistic Network Assumptions
Sandro Coretti, Matthias Fitzi, Aggelos Kiayias, Giorgos Panagiotakos, Alexander Russell

Throughput, i.e., the amount of payload data processed per unit of time, is a crucial measure of scalability for blockchain consensus mechanisms. This paper revisits the design of secure, high-throughput proof-of-stake (PoS) protocols in the \emph{permissionless} setting. Existing high-throughput protocols are either analyzed using overly simplified network models or are designed for permissioned settings, with the task of adapting them to a permissionless environment...

2025/176 (PDF) Last updated: 2025-02-05
HyperLoop: Rationally secure efficient cross-chain bridge
Aniket Kate, Easwar Vivek Mangipudi, Charan Nomula, Raghavendra Ramesh, Athina Terzoglou, Joshua Tobkin
Cryptographic protocols

Cross-chain bridges, realizing the transfer of information and assets between blockchains, form the core of blockchain interoperability solutions. Most existing bridge networks are modeled in an honest-malicious setting, where the bridge nodes are either honest or malicious. Rationality allows the nodes to deviate from the protocol arbitrarily for an economic incentive. In this work, we present HyperLoop, an efficient cross-chain multi-signature bridge and prove that it is safe and live...

2025/023 (PDF) Last updated: 2025-01-06
Cryptography is Rocket Science: Analysis of BPSec
Benjamin Dowling, Britta Hale, Xisen Tian, Bhagya Wimalasiri
Cryptographic protocols

Space networking has become an increasing area of development with the advent of commercial satellite networks such as those hosted by Starlink and Kuiper, and increased satellite and space presence by governments around the world. Yet, historically such network designs have not been made public, leading to limited formal cryptographic analysis of the security offered by them. One of the few public protocols used in space networking is the Bundle Protocol, which is secured by Bundle Protocol...

2024/2091 (PDF) Last updated: 2024-12-29
Encrypted Multi-map that Hides Query, Access, and Volume Patterns
Alexandra Boldyreva, Tianxin Tang

We present an encrypted multi-map, a fundamental data structure underlying searchable encryption/structured encryption. Our protocol supports updates and is designed for applications demanding very strong data security. Not only it hides the information about queries and data, but also the query, access, and volume patterns. Our protocol utilizes a position-based ORAM and an encrypted dictionary. We provide two instantiations of the protocol, along with their operation-type-revealing...

2024/2041 (PDF) Last updated: 2024-12-18
SeaSearch: Secure and Efficient Selection Queries
Shantanu Sharma, Yin Li, Sharad Mehrotra, Nisha Panwar, Komal Kumari, Swagnik Roychoudhury
Applications

Information-theoretic or unconditional security provides the highest level of security --- independent of the computational capability of an adversary. Secret-sharing techniques achieve information-theoretic security by splitting a secret into multiple parts (called shares) and storing the shares across non-colluding servers. However, secret-sharing-based solutions suffer from high overheads due to multiple communication rounds among servers and/or information leakage due to access-patterns...

2024/1911 (PDF) Last updated: 2025-01-10
Deletions and Dishonesty: Probabilistic Data Structures in Adversarial Settings
Mia Filić, Keran Kocher, Ella Kummer, Anupama Unnikrishnan
Applications

Probabilistic data structures (PDS) are compact representations of high-volume data that provide approximate answers to queries about the data. They are commonplace in today's computing systems, finding use in databases, networking and more. While PDS are designed to perform well under benign inputs, they are frequently used in applications where inputs may be adversarially chosen. This may lead to a violation of their expected behaviour, for example an increase in false positive rate. In...

2024/1864 (PDF) Last updated: 2024-11-29
Tweakable ForkCipher from Ideal Block Cipher
Sougata Mandal
Secret-key cryptography

In ASIACRYPT 2019, Andreeva et al. introduced a new symmetric key primitive called the $\textit{forkcipher}$, designed for lightweight applications handling short messages. A forkcipher is a keyed function with a public tweak, featuring fixed-length input and fixed-length (expanding) output. They also proposed a specific forkcipher, ForkSkinny, based on the tweakable block cipher SKINNY, and its security was evaluated through cryptanalysis. Since then, several efficient AEAD and MAC schemes...

2024/1648 (PDF) Last updated: 2024-10-15
SIMD-style Sorting of Integer Sequence in RLWE Ciphertext
Zijing Li, Hongbo Li, Zhengyang Wang
Implementation

This article discusses fully homomorphic encryption and homomorphic sorting. Homomorphic encryption is a special encryption technique that allows all kinds of operations to be performed on ciphertext, and the result is still decryptable, such that when decrypted, the result is the same as that obtained by performing the same operation on the plaintext. Homomorphic sorting is an important problem in homomorphic encryption. Currently, there has been a volume of work on homomorphic sorting. In...

2024/1633 (PDF) Last updated: 2024-10-11
Efficient Boolean-to-Arithmetic Mask Conversion in Hardware
Aein Rezaei Shahmirzadi, Michael Hutter
Implementation

Masking schemes are key in thwarting side-channel attacks due to their robust theoretical foundation. Transitioning from Boolean to arithmetic (B2A) masking is a necessary step in various cryptography schemes, including hash functions, ARX-based ciphers, and lattice-based cryptography. While there exists a significant body of research focusing on B2A software implementations, studies pertaining to hardware implementations are quite limited, with the majority dedicated solely to creating...

2024/1562 (PDF) Last updated: 2024-10-04
Fully Privacy-preserving Billing Models for Peer-to-Peer Electricity Trading Markets
Akash Madhusudan, Mustafa A. Mustafa, Hilder V.L. Pereira, Erik Takke
Cryptographic protocols

Peer-to-peer energy trading markets enable users to exchange electricity, directly offering them increased financial benefits. However, discrepancies often arise between the electricity volumes committed to in trading auctions and the volumes actually consumed or injected. Solutions designed to address this issue often require access to sensitive information that should be kept private. This paper presents a novel, fully privacy-preserving billing protocol designed to protect users'...

2024/1471 (PDF) Last updated: 2024-09-20
Communication Efficient Secure and Private Multi-Party Deep Learning
Sankha Das, Sayak Ray Chowdhury, Nishanth Chandran, Divya Gupta, Satya Lokam, Rahul Sharma
Applications

Distributed training that enables multiple parties to jointly train a model on their respective datasets is a promising approach to address the challenges of large volumes of diverse data for training modern machine learning models. However, this approach immedi- ately raises security and privacy concerns; both about each party wishing to protect its data from other parties during training and preventing leakage of private information from the model after training through various...

2024/1301 (PDF) Last updated: 2024-08-20
Kalos: Hierarchical-auditable and Human-binding Authentication Scheme for Clinical Trial
Chang Chen, Zelong Wu, Guoyu Yang, Qi Chen, Wei Wang, Jin Li
Public-key cryptography

Clinical trials are crucial in the development of new medical treatment methods. To ensure the correctness of clinical trial results, medical institutes need to collect and process large volumes of participant data, which has prompted research on privacy preservation and data reliability. However, existing solutions struggle to resolve the trade-off between them due to the trust gap between the physical and digital worlds, limiting their practicality. To tackle the issues above, we present...

2024/1190 (PDF) Last updated: 2024-07-23
Efficient Two-Party Secure Aggregation via Incremental Distributed Point Function
Nan Cheng, Aikaterini Mitrokotsa, Feng Zhang, Frank Hartmann
Cryptographic protocols

Computing the maximum from a list of secret inputs is a widely-used functionality that is employed ei- ther indirectly as a building block in secure computation frameworks, such as ABY (NDSS’15) or directly used in multiple applications that solve optimisation problems, such as secure machine learning or secure aggregation statistics. Incremental distributed point function (I-DPF) is a powerful primitive (IEEE S&P’21) that significantly reduces the client- to-server communication and are...

2024/1021 (PDF) Last updated: 2025-03-20
ammBoost: State Growth Control for AMMs
Nicolas Michel, Mohamed E. Najd, Ghada Almashaqbeh
Cryptographic protocols

Automated market makers (AMMs) are a prime example of Web 3.0 applications. Their popularity and high trading activity led to serious scalability issues in terms of throughput and state size. In this paper, we address these challenges by utilizing a new sidechain architecture, building a system called ammBoost. ammBoost reduces the amount of on-chain transactions, boosts throughput, and supports blockchain pruning. We devise several techniques to enable layer 2 processing for AMMs, including...

2024/556 (PDF) Last updated: 2024-05-22
Menhir: An Oblivious Database with Protection against Access and Volume Pattern Leakage
Leonie Reichert, Gowri R Chandran, Phillipp Schoppmann, Thomas Schneider, Björn Scheuermann
Applications

Analyzing user data while protecting the privacy of individuals remains a big challenge. Trusted execution environments (TEEs) are a possible solution as they protect processes and Virtual Machines (VMs) against malicious hosts. However, TEEs can leak access patterns to code and to the data being processed. Furthermore, when data is stored in a TEE database, the data volume required to answer a query is another unwanted side channel that contains sensitive information. Both types of...

2024/516 (PDF) Last updated: 2024-11-24
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...

2024/498 (PDF) Last updated: 2024-04-01
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...

2024/330 (PDF) Last updated: 2024-05-20
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...

2023/1955 (PDF) Last updated: 2023-12-25
Barrett Multiplication for Dilithium on Embedded Devices
Vincent Hwang, YoungBeom Kim, Seog Chung Seo
Implementation

We optimize the number-theoretic transforms (NTTs) in Dilithium — a digital signature scheme recently standardized by the National Institute of Standards and Technology (NIST) — on Cortex-M3 and 8-bit AVR. The core novelty is the exploration of micro-architectural insights for modular multiplications. Recent work [Becker, Hwang, Kannwischer, Yang and Yang, Volume 2022 (1), Transactions on Cryptographic Hardware and Embedded Systems, 2022] found a correspondence between Montgomery and Barrett...

2023/1921 (PDF) Last updated: 2023-12-15
Automated Issuance of Post-Quantum Certificates: a New Challenge
Alexandre Augusto Giron, Frederico Schardong, Lucas Pandolfo Perin, Ricardo Custódio, Victor Valle, Víctor Mateu

The Automatic Certificate Management Environment protocol (ACME) has significantly contributed to the widespread use of digital certificates in safeguarding the authenticity and privacy of Internet data. These certificates are required for implementing the Transport Layer Security (TLS) protocol. However, it is well known that the cryptographic algorithms employed in these certificates will become insecure with the emergence of quantum computers. This study assesses the challenges in...

2023/1842 (PDF) Last updated: 2025-01-03
Leverage Staking with Liquid Staking Derivatives (LSDs): Opportunities and Risks
Xihan Xiong, Zhipeng Wang, Xi Chen, William Knottenbelt, Michael Huth
Applications

In the Proof of Stake (PoS) Ethereum ecosystem, users can stake ETH on Lido to receive stETH, a Liquid Staking Derivative (LSD) that represents staked ETH and accrues staking rewards. LSDs improve the liquidity of staked assets by facilitating their use in secondary markets, such as for collateralized borrowing on Aave or asset exchanges on Curve. The composability of Lido, Aave, and Curve enables an emerging strategy known as leverage staking, an iterative process that enhances financial...

2023/1712 (PDF) Last updated: 2023-11-05
Beyond Volume Pattern: Storage-Efficient Boolean Searchable Symmetric Encryption with Suppressed Leakage
Feng Li, Jianfeng Ma, Yinbin Miao, Pengfei Wu, Xiangfu Song
Cryptographic protocols

Boolean Searchable Symmetric Encryption (BSSE) enables users to perform retrieval operations on the encrypted data while sup- porting complex query capabilities. This paper focuses on addressing the storage overhead and privacy concerns associated with existing BSSE schemes. While Patel et al. (ASIACRYPT’21) and Bag et al. (PETS’23) introduced BSSE schemes that conceal the number of single keyword re- sults, both of them suffer from quadratic storage overhead and neglect the privacy of...

2023/1529 (PDF) Last updated: 2024-08-22
Shufflecake: Plausible Deniability for Multiple Hidden Filesystems on Linux
Elia Anzuoni, Tommaso Gagliardoni
Applications

We present Shufflecake, a new plausible deniability design to hide the existence of encrypted data on a storage medium making it very difficult for an adversary to prove the existence of such data. Shufflecake can be considered a ``spiritual successor'' of tools such as TrueCrypt and VeraCrypt, but vastly improved: it works natively on Linux, it supports any filesystem of choice, and can manage multiple volumes per device, so to make deniability of the existence of hidden partitions really...

2023/1366 (PDF) Last updated: 2023-09-25
Compact Frequency Estimators in Adversarial Environments
Sam A. Markelon, Mia Filić, Thomas Shrimpton
Applications

Count-Min Sketch (CMS) and HeavyKeeper (HK) are two realizations of a compact frequency estimator (CFE). These are a class of probabilistic data structures that maintain a compact summary of (typically) high-volume streaming data, and provides approximately correct estimates of the number of times any particular element has appeared. CFEs are often the base structure in systems looking for the highest-frequency elements (i.e., top-$K$ elements, heavy hitters, elephant flows). ...

2023/983 (PDF) Last updated: 2024-04-08
Secure Range-Searching Using Copy-And-Recurse
Eyal Kushnir, Guy Moshkowich, Hayim Shaul
Cryptographic protocols

{\em Range searching} is the problem of preprocessing a set of points $P$, such that given a query range $\gamma$ we can efficiently compute some function $f(P\cap\gamma)$. For example, in a 1 dimensional {\em range counting} query, $P$ is a set of numbers, $\gamma$ is a segment and we need to count how many numbers of $P$ are in $\gamma$. In higher dimensions, $P$ is a set of $d$ dimensional points and the query range is some volume in $R^d$. In general, we want to compute more than just...

2023/973 (PDF) Last updated: 2023-08-30
Demystifying Just-in-Time (JIT) Liquidity Attacks on Uniswap V3
Xihan Xiong, Zhipeng Wang, William Knottenbelt, Michael Huth
Applications

Uniswap is currently the most liquid Decentralized Exchange (DEX) on Ethereum. In May 2021, it upgraded to the third protocol version named Uniswap V3. The key feature update is “concentrated liquidity”, which supports liquidity provision within custom price ranges. However, this design introduces a new type of Miner Extractable Value (MEV) source called Just-in-Time (JIT) liquidity attack, where the adversary mints and burns a liquidity position right before and after a sizable swap. We...

2023/903 (PDF) Last updated: 2025-01-27
Near-Optimal Oblivious Key-Value Stores for Efficient PSI, PSU and Volume-Hiding Multi-Maps
Alexander Bienstock, Sarvar Patel, Joon Young Seo, Kevin Yeo
Cryptographic protocols

In this paper, we study oblivious key-value stores (OKVS) that enable encoding n key-value pairs into length $m$ encodings while hiding the input keys. The goal is to obtain high rate, $n/m$, with efficient encoding and decoding algorithms. We present $\mathsf{RB\text{-}OKVS}$ built on random band matrices that obtains near-optimal rates as high as 0.97 whereas prior works could only achieve rates up to 0.81 with similar encoding times. Using $\mathsf{RB\text{-}OKVS}$, we obtain...

2023/892 (PDF) Last updated: 2024-05-22
Suboptimality in DeFi
Aviv Yaish, Maya Dotan, Kaihua Qin, Aviv Zohar, Arthur Gervais
Applications

The decentralized finance (DeFi) ecosystem has proven to be popular in facilitating financial operations, such as token exchange and lending. The public availability of DeFi platforms’ code, together with real-time data on all user interactions with them, has given rise to complex tools that find and seize profit opportunities on behalf of users. In this work, we show that both users and the aforementioned tools sometimes act suboptimally: their profits can be increased by more than 100%,...

2023/890 (PDF) Last updated: 2023-06-09
Efficient Evaluation of Frequency Test for Overlapping Vectors Statistic
Krzysztof MAŃK
Foundations

Randomness testing is one of the essential and easiest tools for evaluating cryptographic primitives. The faster we can test, the greater volume of data that can be tested. Thus a more detailed analysis is possible. This paper presents a range of observations made for a well-known frequency test for overlapping vectors in binary sequence testing. We have obtained precise chi-square statistic computed in $O \left(dt 2^{dt} \right)$ instead of $O\left( 2^{2dt}\right)$ time, without precomputed tables.

2023/813 (PDF) Last updated: 2025-04-01
Bayesian Leakage Analysis: A Framework for Analyzing Leakage in Cryptography
Zachary Espiritu, Seny Kamara, Tarik Moataz
Foundations

We introduce a framework based on Bayesian statistical inference for analyzing leakage in cryptography and its vulnerability to inference attacks. Our framework naturally integrates auxiliary information, defines a notion of adversarial advantage, and provides information-theoretic measures that capture the security of leakage patterns against both full and functional recovery attacks. We present two main theorems that bound the advantage of powerful inference techniques: the maximum a...

2023/720 (PDF) Last updated: 2024-07-26
MUSES: Efficient Multi-User Searchable Encrypted Database
Tung Le, Rouzbeh Behnia, Jorge Guajardo, Thang Hoang
Cryptographic protocols

Searchable encrypted systems enable privacy-preserving keyword search on encrypted data. Symmetric systems achieve high efficiency (e.g., sublinear search), but they mostly support single-user search. Although systems based on public-key or hybrid models support multi-user search, they incur inherent security weaknesses (e.g., keyword-guessing vulnerabilities) and scalability limitations due to costly public-key operations (e.g., pairing). More importantly, most encrypted search designs leak...

2023/533 (PDF) Last updated: 2023-04-13
Injection-Secure Structured and Searchable Symmetric Encryption
Ghous Amjad, Seny Kamara, Tarik Moataz
Cryptographic protocols

Recent work on dynamic structured and searchable symmetric encryption has focused on achieving the notion of forward-privacy. This is mainly motivated by the claim that forward-privacy protects against adaptive file injection attacks (Zhang, Katz, Papamanthou, Usenix Security, 2016). In this work, we revisit the notion of forward-privacy in several respects. First, we observe that forward-privacy does not necessarily guarantee security against adaptive file injection attacks if a scheme...

2023/373 (PDF) Last updated: 2023-03-15
Consensus Algorithm Using Transaction History for Cryptocurrency
Yuuki Komi, Takayuki Tatekawa
Cryptographic protocols

Blockchain consensus algorithms for cryptocurrency consist of the proof of work and proof of stake. However, current algorithms have problems, such as huge power consumption and equality issues. We propose a new consensus algorithm that uses transaction history. This algorithm ensures equality by randomly assigning approval votes based on past transaction records. We also incorporate a mechanism for adjusting issuance volume to measure the stability of the currency's value.

2022/1712 (PDF) Last updated: 2022-12-10
KEMTLS vs. Post-Quantum TLS: Performance On Embedded Systems
Ruben Gonzalez, Thom Wiggers
Implementation

TLS is ubiquitous in modern computer networks. It secures transport for high-end desktops and low-end embedded devices alike. However, the public key cryptosystems currently used within TLS may soon be obsolete as large-scale quantum computers, once realized, would be able to break them. This threat has led to the development of post-quantum cryptography (PQC). The U.S. standardization body NIST is currently in the process of concluding a multi-year search for promising post-quantum...

2022/1679 (PDF) Last updated: 2022-12-02
Integer Polynomial Recovery from Outputs and its Application to Cryptanalysis of a Protocol for Secure Sorting
Srinivas Vivek, Shyam Murthy, Deepak Kumaraswamy
Attacks and cryptanalysis

{We investigate the problem of recovering integer inputs (up to an affine scaling) when given only the integer monotonic polynomial outputs. Given $n$ integer outputs of a degree-$d$ integer monotonic polynomial whose coefficients and inputs are integers within known bounds and $n \gg d$, we give an algorithm to recover the polynomial and the integer inputs (up to an affine scaling). A heuristic expected time complexity analysis of our method shows that it is exponential in the size of the...

2022/1098 (PDF) Last updated: 2022-08-25
SoK: Security Evaluation of SBox-Based Block Ciphers
Joelle Lim, Derrick Ng, Ruth Ng
Cryptographic protocols

Cryptanalysis of block ciphers is an active and important research area with an extensive volume of literature. For this work, we focus on SBox-based ciphers, as they are widely used and cover a large class of block ciphers. While there have been prior works that have consolidated attacks on block ciphers, they usually focus on describing and listing the attacks. Moreover, the methods for evaluating a cipher's security are often ad hoc, differing from cipher to cipher, as attacks and...

2022/1096 (PDF) Last updated: 2022-08-24
TWo-IN-one-SSE: Fast, Scalable and Storage-Efficient Searchable Symmetric Encryption for Conjunctive and Disjunctive Boolean Queries
Arnab Bag, Debadrita Talapatra, Ayushi Rastogi, Sikhar Patranabis, Debdeep Mukhopadhyay
Applications

Searchable Symmetric Encryption (SSE) supports efficient yet secure query processing over outsourced symmetrically encrypted databases without the need for decryption. A longstanding open question has been the following: can we design a fast, scalable, linear storage and low-leakage SSE scheme that efficiently supports arbitrary Boolean queries over encrypted databases? In this paper, we present the design, analysis and prototype implementation of the first SSE scheme that efficiently...

2022/1037 (PDF) Last updated: 2022-12-22
RPM: Robust Anonymity at Scale
Donghang Lu, Aniket Kate
Cryptographic protocols

This work presents RPM, a scalable anonymous communication protocol suite using secure multiparty computation (MPC) with the offline-online model. We generate random, unknown permutation matrices in a secret-shared fashion and achieve improved (online) performance and the lightest communication and computation overhead for the clients compared to the state of art robust anonymous communication protocols. Using square-lattice shuffling, we make our protocol scale well as the number of...

2022/1011 (PDF) Last updated: 2022-08-05
Structure-Aware Private Set Intersection, With Applications to Fuzzy Matching
Gayathri Garimella, Mike Rosulek, Jaspal Singh
Cryptographic protocols

In two-party private set intersection (PSI), Alice holds a set $X$, Bob holds a set $Y$, and they learn (only) the contents of $X \cap Y$. We introduce structure-aware PSI protocols, which take advantage of situations where Alice's set $X$ is publicly known to have a certain structure. The goal of structure-aware PSI is to have communication that scales with the description size of Alice's set, rather its cardinality. We introduce a new generic paradigm for structure-aware...

2022/947 (PDF) Last updated: 2022-07-22
Volume and Access Pattern Leakage-abuse Attack with Leaked Documents
Steven Lambregts, Huanhuan Chen, Jianting Ning, Kaitai Liang
Attacks and cryptanalysis

Searchable Encryption schemes provide secure search over encrypted databases while allowing admitted information leakages. Generally, the leakages can be categorized into access and volume pattern. In most existing SE schemes, these leakages are caused by practical designs but are considered an acceptable price to achieve high search efficiency. Recent attacks have shown that such leakages could be easily exploited to retrieve the underlying keywords for search queries. Under the umbrella of...

2022/924 (PDF) Last updated: 2022-07-15
FICS PCB X-ray: A dataset for automated printed circuit board inter-layers inspection
Dhwani Mehta, John True, Olivia P. Dizon-Paradis, Nathan Jessurun, Damon L. Woodard, Navid Asadizanjani, Mark Tehranipoor
Applications

Advancements in computer vision and machine learning breakthroughs over the years have paved the way for automated X-ray inspection (AXI) of printed circuit boards (PCBs). However, there is no standard dataset to verify the capabilities and limitations of such advancements in practice due to the lack of publicly available datasets for PCB X-ray inspection. Furthermore, there is a lack of diverse PCB X-ray datasets that encompass images from X-ray Computed Tomography (CT). To address the lack...

2022/894 (PDF) Last updated: 2022-07-08
Toward Full Accounting for Leakage Exploitation and Mitigation in Dynamic Encrypted Databases
Lei Xu, Anxin Zhou, Huayi Duan, Cong Wang, Qian Wang, Xiaohua Jia

Encrypted database draws much attention as it provides privacy-protection services for sensitive data outsourced to a third party. Recent studies show that the security guarantee of encrypted databases are challenged by several leakage-abuse attacks on its search module, and corresponding countermeasures are also proposed. Most of these studies focus on static databases, yet the case for dynamic has not been well investigated. To fill this gap, in this paper, we focus on exploring privacy...

2022/808 (PDF) Last updated: 2022-08-01
Secret key generation from Gaussian sources using lattice-based extractors
Laura Luzzi, Cong Ling, Matthieu R. Bloch
Foundations

We propose a lattice-based scheme for secret key generation from Gaussian sources in the presence of an eavesdropper, and show that it achieves the strong secret key capacity in the case of degraded source models, as well as the optimal secret key / public communication rate trade-off. The key ingredients of our scheme are a lattice extractor to extract the channel intrinsic randomness, based on the notion of flatness factor, together with a randomized lattice quantization technique to...

2022/714 (PDF) Last updated: 2025-01-31
MicroSecAgg: Streamlined Single-Server Secure Aggregation
Yue Guo, Antigoni Polychroniadou, Elaine Shi, David Byrd, Tucker Balch
Cryptographic protocols

This work introduces MicroSecAgg, a framework that addresses the intricacies of secure aggregation in the single-server landscape, specifically tailored to situations where distributed trust among multiple non-colluding servers presents challenges. Our protocols are purpose-built to handle situations featuring multiple successive aggregation phases among a dynamic pool of clients who can drop out during the aggregation. Our different protocols thrive in three distinct cases: firstly, secure...

2022/675 (PDF) Last updated: 2022-06-24
MPClan: Protocol Suite for Privacy-Conscious Computations
Nishat Koti, Shravani Patil, Arpita Patra, Ajith Suresh
Cryptographic protocols

The growing volumes of data being collected and its analysis to provide better services are creating worries about digital privacy. To address privacy concerns and give practical solutions, the literature has relied on secure multiparty computation. However, recent research has mostly focused on the small-party honest-majority setting of up to four parties, noting efficiency concerns. In this work, we extend the strategies to support a larger number of participants in an honest-majority...

2022/451 (PDF) Last updated: 2025-02-23
Improved Stock Market Structure Using Cryptography
Charanjit S. Jutla, Barry Mishra
Applications

The stock market has two primary functions, that of providing liquidity and price discovery. While historically, the market micro-structure was mostly ignored or assumed to function ideally for the purpose of asset pricing, O’Hara (Journal of Finance, 2003) established that both liquidity and price discovery affect asset pricing, and consequently asset returns. In this work, we extend the analysis of Easley and O’Hara (Journal of finance, 2004) to study common stock market mechanisms,...

2022/388 (PDF) Last updated: 2022-03-28
Shaduf++: Non-Cycle and Privacy-Preserving Payment Channel Rebalancing
Zhonghui Ge, Yi Zhang, Yu Long, Dawu Gu
Cryptographic protocols

A leading approach to enhancing the performance and scalability of permissionless blockchains is to use the payment channel, which allows two users to perform off-chain payments with almost unlimited frequency. By linking payment channels together to form a payment channel network, users connected by a path of channels can perform off-chain payments rapidly. However, payment channels risk encountering fund depletion, which threatens the availability of both the payment channel and network....

2022/090 (PDF) Last updated: 2022-01-25
Attacks on Encrypted Range Search Schemes in Multiple Dimensions
Francesca Falzon, Evangelia Anna Markatou, Zachary Espiritu, Roberto Tamassia
Applications

We present the first systematic security evaluation of multi-attribute range search schemes on symmetrically encrypted data. We present four database reconstruction attacks that apply to a broad class of schemes and rely on volume and search pattern leakage. For schemes achieving efficiency by decomposing a query into a small number of subqueries, we further show how to exploit their structure pattern, i.e., co-occurrences of subqueries. We introduce a flexible framework for building secure...

2021/1704 (PDF) Last updated: 2024-04-26
Verifiable Encryption from MPC-in-the-Head
Akira Takahashi, Greg Zaverucha

Verifiable encryption (VE) is a protocol where one can provide assurance that an encrypted plaintext satisfies certain properties, or relations. It is an important building block in cryptography with many useful applications, such as key escrow, group signatures, optimistic fair exchange, and others. However, the majority of previous VE schemes are restricted to instantiation with specific public-key encryption schemes or relations. In this work, we propose a novel framework that...

2021/1643 (PDF) Last updated: 2021-12-17
STROBE: Stake-based Threshold Random Beacons
Donald Beaver, Konstantinos Chalkias, Mahimna Kelkar, Lefteris Kokoris Kogias, Kevin Lewi, Ladi de Naurois, Valeria Nicolaenko, Arnab Roy, Alberto Sonnino
Cryptographic protocols

We revisit decentralized random beacons with a focus on practical distributed applications. Decentralized random beacons (Beaver and So, Eurocrypt 1993) provide the functionality for $n$ parties to generate an unpredictable sequence of bits in a way that cannot be biased, which is useful for any decentralized protocol requiring trusted randomness. Existing beacon constructions are highly inefficient in practical settings where protocol parties need to rejoin after crashes or disconnections,...

2021/1593 (PDF) Last updated: 2021-12-06
Interpreting and Mitigating Leakage-abuse Attacks in Searchable Symmetric Encryption
Lei Xu, Huayi Duan, Anxin Zhou, Xingliang Yuan, Cong Wang
Foundations

Searchable symmetric encryption (SSE) enables users to make confidential queries over always encrypted data while confining information disclosure to pre-defined leakage profiles. Despite the well-understood performance and potentially broad applications of SSE, recent leakage-abuse attacks (LAAs) are questioning its real-world security implications. They show that a passive adversary with certain prior information of a database can recover queries by exploiting the legitimately admitted...

2021/1549 (PDF) Last updated: 2021-12-06
Kicking-the-Bucket: Fast Privacy-Preserving Trading Using Buckets
Mariana Botelho da Gama, John Cartlidge, Antigoni Polychroniadou, Nigel P. Smart, Younes Talibi Alaoui
Applications

We examine bucket-based and volume-based algorithms for privacy-preserving asset trading in a financial dark pool. Our bucket-based algorithm places orders in quantised buckets, whereas the volume-based algorithm allows any volume size but requires more complex validation mechanisms. In all cases, we conclude that these algorithms are highly efficient and offer a practical solution to the commercial problem of preserving privacy of order information in a dark pool trading venue.

2021/1346 (PDF) Last updated: 2021-10-07
WeStat: a Privacy-Preserving Mobile Data Usage Statistics System
Sébastien Canard, Nicolas Desmoulins, Sébastien Hallay, Adel Hamdi, Dominique Le Hello
Applications

The preponderance of smart devices, such as smartphones, has boosted the development and use of mobile applications (apps) in the recent years. This prevalence induces a large volume of mobile app usage data. The analysis of such information could lead to a better understanding of users' behaviours in using the apps they have installed, even more if these data can be coupled with a given context (location, time, date, sociological data...). However, mobile and apps usage data are very...

2021/1140 (PDF) Last updated: 2021-09-10
Computing Discrete Logarithms
Robert Granger, Antoine Joux
Public-key cryptography

We describe some cryptographically relevant discrete logarithm problems (DLPs) and present some of the key ideas and constructions behind the most efficient algorithms known that solve them. Since the topic encompasses such a large volume of literature, for the finite field DLP we limit ourselves to a selection of results reflecting recent advances in fixed characteristic finite fields.

2021/879 (PDF) Last updated: 2022-07-19
Rethinking Searchable Symmetric Encryption
Zichen Gui, Kenneth G. Paterson, Sikhar Patranabis
Applications

Symmetric Searchable Encryption (SSE) schemes enable keyword searches over encrypted documents. To obtain efficiency, SSE schemes incur a certain amount of leakage. The vast majority of the literature on SSE considers only leakage from one component of the overall SSE system, the encrypted search index. This component is used to identify which documents to return in response to a keyword query. The actual fetching of the documents is left to another component, usually left unspecified in the...

2021/816 (PDF) Last updated: 2021-06-16
Privacy-Preserving Approximate k-Nearest-Neighbors Search that Hides Access, Query and Volume Patterns
Alexandra Boldyreva, Tianxin Tang
Cryptographic protocols

We study the problem of privacy-preserving approximate kNN search in an outsourced environment — the client sends the encrypted data to an untrusted server and later can perform secure approximate kNN search and updates. We design a security model and propose a generic construction based on locality-sensitive hashing, symmetric encryption, and an oblivious map. The construction provides very strong security guarantees, not only hiding the information about the data, but also the access,...

2021/786 (PDF) Last updated: 2021-06-14
Volume-Hiding Dynamic Searchable Symmetric Encryption with Forward and Backward Privacy
Yongjun Zhao, Huaxiong Wang, Kwok-Yan Lam
Foundations

Volumetric leakage in encrypted databases had been overlooked by the community for a long time until Kellaris et al. (CCS ’16) proposed the first database reconstruction attack leveraging communication volume. Their attack was soon improved and several query recovery attacks were discovered recently. In response to the advancements of volumetric leakage attacks, volume-hiding searchable symmetric encryption (SSE) schemes have been proposed (Kamara and Moataz, Eurocrypt ’19 & Patel et al.,...

2021/765 (PDF) Last updated: 2023-07-11
Dynamic Volume-Hiding Encrypted Multi-Maps with Applications to Searchable Encryption
Ghous Amjad, Sarvar Patel, Giuseppe Persiano, Kevin Yeo, Moti Yung
Cryptographic protocols

We study encrypted storage schemes where a client outsources data to an untrusted third-party server (such as a cloud storage provider) while maintaining the ability to privately query and dynamically update the data. We focus on encrypted multi-maps (EMMs), a structured encryption (STE) scheme that stores pairs of label and value tuples. EMMs allow queries on labels and return the associated value tuple. As responses are variable-length, EMMs are subject to volume leakage attacks introduced...

2021/648 (PDF) Last updated: 2022-02-22
Security of COFB against Chosen Ciphertext Attacks
Mustafa Khairallah
Secret-key cryptography

COFB is a lightweight Authenticated Encryption with Associated Data (AEAD) mode based on block ciphers. It was proposed in CHES 2017 and is the basis for GIFT-COFB, a finalist in the NIST lightweight standardization project. It comes with provable security results that guarantee its security up to the birthday bound in the nonce-respecting model. However, the designers offer multiple versions of the analysis with different details and the implications of attacks against the scheme are not...

2021/631 (PDF) Last updated: 2022-08-30
SwapCT: Swap Confidential Transactions for Privacy-Preserving Multi-Token Exchanges
Felix Engelmann, Lukas Müller, Andreas Peter, Frank Kargl, Christoph Bösch
Cryptographic protocols

Decentralized token exchanges allow for secure trading of tokens without a trusted third party. However, decentralization is mostly achieved at the expense of transaction privacy. For a fair exchange, transactions must remain private to hide the participants and volumes while maintaining the possibility for non-interactive execution of trades. In this paper we present a swap confidential transaction system (SwapCT) which is related to ring confidential transactions (e.g. used in Monero) but...

2021/455 (PDF) Last updated: 2021-10-14
Guessing Bits: Improved Lattice Attacks on (EC)DSA with Nonce Leakage
Chao Sun, Thomas Espitau, Mehdi Tibouchi, Masayuki Abe
Public-key cryptography

The lattice reduction attack on (EC)DSA (and other Schnorr-like signature schemes) with partially known nonces, originally due to Howgrave-Graham and Smart, has been at the core of many concrete cryptanalytic works, side-channel based or otherwise, in the past 20 years. The attack itself has seen limited development, however: improved analyses have been carried out, and the use of stronger lattice reduction algorithms has pushed the range of practically vulnerable parameters further, but...

2021/374 (PDF) Last updated: 2021-09-22
ZXAD: High-volume Attack Mitigation for Tor
Akshaya Mani, Ian Goldberg
Applications

The Tor anonymity network is often abused by some attackers to (anonymously) convey attack traffic. These attacks abuse Tor exit relays (i.e., the relays through which traffic exits Tor) by making it appear the attack originates there; as a result, many website operators indiscriminately block all Tor traffic (by blacklisting all exit IPs), reducing the usefulness of Tor. Recent research shows that majority of these attacks are ones that generate high traffic volume (e.g., Denial-of-Service...

2021/143 (PDF) Last updated: 2021-06-03
On Bitcoin Cash’s Target Recalculation Functions
Juan Garay, Yu Shen
Cryptographic protocols

Bitcoin Cash, created in 2017, is a “hard fork” from Bitcoin responding to the need for allowing a higher transaction volume. This is achieved by a larger block size, as well as a new difficulty adjustment (target recalculation) function(s) that acts more frequently (as opposed to Bitcoin’s difficulty adjustment happening about every two weeks), resulting in a potentially different target for each block. While seemingly achieving its goal in practice, to our knowledge there is no formal...

2021/093 (PDF) Last updated: 2021-06-09
Response-Hiding Encrypted Ranges: Revisiting Security via Parametrized Leakage-Abuse Attacks
Evgenios M. Kornaropoulos, Charalampos Papamanthou, Roberto Tamassia

Despite a growing body of work on leakage-abuse attacks for encrypted databases, attacks on practical response-hiding constructions are yet to appear. Response-hiding constructions are superior in that they nullify access-pattern based attacks by revealing only the search token and the result size of each query. Response-hiding schemes are vulnerable to existing volume attacks, which are, however, based on strong assumptions such as the uniform query assumption or the dense database...

2021/055 (PDF) Last updated: 2021-01-18
Tech Report: Inerial HSMs Thwart Advanced Physical Attacks
Jan Sebastian Götte, Björn Scheuermann
Implementation

In this tech report, we introduce a novel countermeasure against physical attacks: Inertial hardware security modules (iHSMs). Conventional systems have in common that they try to detect attacks by crafting sensors responding to increasingly minute manipulations of the monitored security boundary or volume. Our approach is novel in that we reduce the sensitivity requirement of security meshes and other sensors and increase the complexity of any manipulations by rotating the security mesh or...

2020/1394 (PDF) Last updated: 2020-11-10
Practical and Secure Circular Range Search on Private Spatial Data
Zhihao Zheng, Jiachen Shen, Zhenfu Cao
Secret-key cryptography

With the location-based services (LBS) booming, the volume of spatial data inevitably explodes. In order to reduce local storage and computational overhead, users tend to outsource data and initiate queries to the cloud. However, sensitive data or queries may be compromised if cloud server has access to raw data and plaintext token. To cope with this problem, searchable encryption for geometric range is applied. Geometric range search has wide applications in many scenarios, especially the...

2020/1328 (PDF) Last updated: 2023-08-21
SWiSSSE: System-Wide Security for Searchable Symmetric Encryption
Zichen Gui, Kenneth G. Paterson, Sikhar Patranabis, Bogdan Warinschi
Applications

This paper initiates a new direction in the design and analysis of searchable symmetric encryption (SSE) schemes. We provide the first comprehensive security model and definition for SSE that takes into account leakage from the entirety of the SSE system, including not only from access to encrypted indices but also from access to the encrypted database documents themselves. Such system-wide leakage is intrinsic in end-to-end SSE systems, and can be used to break almost all state-of-the-art...

2020/1241 (PDF) Last updated: 2020-10-09
DAPA: Differential Analysis aided Power Attack on (Non-)Linear Feedback Shift Registers (Extended version)
Siang Meng Sim, Dirmanto Jap, Shivam Bhasin
Secret-key cryptography

Differential power analysis (DPA) is a form of side-channel analysis (SCA) that performs statistical analysis on the power traces of cryptographic computations. DPA is applicable to many cryptographic primitives, including block ciphers, stream ciphers and even hash-based message authentication code (HMAC). At COSADE 2017, Dobraunig~et~al. presented a DPA on the fresh re-keying scheme Keymill to extract the bit relations of neighbouring bits in its shift registers, reducing the internal...

2020/1055 (PDF) Last updated: 2020-09-01
Synced Hash-Based Signatures: Post-Quantum Authentication in a Blockchain
Santi J. Vives
Public-key cryptography

A new post-quantum, hash-based signature (HBS) scheme is introduced. In known HBS, the size and cost of each signature increase as the total number of messages one wishes to authenticate increase. In real-world applications, requiring large volumes of signatures, they can become impractical. This paper studies HBS in a blockchain: a public, decentralized database. The proposed HBS scheme shows that, when all signatures are known, quite the opposite is possible: the signatures can become more...

2020/1052 (PDF) Last updated: 2020-09-01
Attacking Threshold Wallets
Jean-Philippe Aumasson, Omer Shlomovits
Applications

Threshold wallets leverage threshold signature schemes (TSS) to distribute signing rights across multiple parties when issuing blockchain transactions. These provide greater assurance against insider fraud, and are sometimes seen as an alternative to methods using a trusted execution environment to issue the signature. This new class of applications motivated researchers to discover better protocols, entrepreneurs to create start-up companies, and large organizations to deploy TSS-based...

2020/858 (PDF) Last updated: 2020-12-07
Client-oblivious OPRAM
Gareth T. Davies, Christian Janson, Daniel P. Martin
Cryptographic protocols

Oblivious Parallel RAM (OPRAM) enables multiple clients to synchronously make read and write accesses to shared memory (more generally, any data-store) whilst hiding the access patterns from the owner/provider of that shared memory. Prior work is best suited to the setting of multiple processors (or cores) within a single client device, and consequently there are shortcomings when applying that work to the multi-client setting where distinct client devices may not trust each other, or may...

2020/830 (PDF) Last updated: 2020-07-07
Terakey - An Encryption Method Whose Security Can Be Analyzed from First Principles
Arnold G. Reinhold
Secret-key cryptography

Terakey is an encryption system whose confidentiality can be demonstrated from first principles, without making assumptions about the computational difficulty of certain mathematical problems. It employs a key that is much larger than the anticipated volume of message traffic. It is based on the one-time pad, but addresses the risk of key reuse stochastically. Conventional cryptographic techniques can be used to ameliorate infrequent byte collisions. The large size of the key reduces the...

2020/673 (PDF) Last updated: 2020-06-11
LotMint: Blockchain Returning to Decentralization with Decentralized Clock
Wenbo MAO, Wenxiang WANG

We present LotMint, a permissionless blockchain, with a purposely low set bar for Proof-of-Work (PoW) difficulty. Our objective is for personal computers, cloud virtual machines or containers, even mobile devices, and hopefully future IoT devices, to become the main, widely distributed, collectively much securer, fairer, more reliable and economically sustainable mining workforce for blockchains. An immediate question arises: how to prevent the permissionless network from being flooded of...

2020/580 (PDF) Last updated: 2020-05-18
TxChain: Efficient Cryptocurrency Light Clients via Contingent Transaction Aggregation
Alexei Zamyatin, Zeta Avarikioti, Daniel Perez, William J. Knottenbelt
Cryptographic protocols

Cryptocurrency light- or simplified payment verification (SPV) clients allow nodes with limited resources to efficiently verify execution of payments. Instead of downloading the entire blockchain, only block headers and selected transactions are stored. Still, the storage and bandwidth cost, linear in blockchain size, remain non-negligible, especially for smart contracts and mobile devices: as of April 2020, these amount to 50 MB in Bitcoin and 5 GB in Ethereum. Recently, two improved...

2020/502 (PDF) Last updated: 2020-04-30
Applying Blockchain Layer2 Technology to Mass E-Commerce
Sijia Zhao, Donal O’Mahony

The emergence of e-commerce has changed the way people trade. However, merchants are charged high fees for their use of the platform and for payment services. These costs are passed on to customers in the form of higher prices. Blockchain technology can provide lower transaction fees with high security and privacy level but is incapable of delivering the number of transactions per second demanded by real e-commerce. Establishing a layer above the blockchain to manage transactions which we...

2020/493 (PDF) Last updated: 2023-05-01
Towards Defeating Mass Surveillance and SARS-CoV-2: The Pronto-C2 Fully Decentralized Automatic Contact Tracing System
Gennaro Avitabile, Vincenzo Botta, Vincenzo Iovino, Ivan Visconti
Cryptographic protocols

Mass surveillance can be more easily achieved leveraging fear and desire of the population to feel protected while affected by devastating events. Indeed, in such scenarios, governments can adopt exceptional measures that limit civil rights, usually receiving large support from citizens. The COVID-19 pandemic is currently affecting daily life of many citizens in the world. People are forced to stay home for several weeks, unemployment rates quickly increase, uncertainty and sadness...

2020/264 (PDF) Last updated: 2020-03-04
Plaintext Recovery Attacks against Linearly Decryptable Fully Homomorphic Encryption Schemes
Nicholas Mainardi, Alessandro Barenghi, Gerardo Pelosi
Public-key cryptography

Homomorphic encryption primitives have the potential to be the main enabler of privacy preserving computation delegation to cloud environments. One of the avenues which has been explored to reduce their significant computational overhead with respect to cleartext computation is the one of the so-called noise-free homomorphic encryption schemes. In this work, we present an attack against fully homomorphic encryption primitives where a distinguisher for a single plaintext value exists. We...

2020/242 Last updated: 2020-11-08
Practical and Secure Circular Range Search on Private Spatial Data
Zhihao Zheng, Jiachen Shen, Zhenfu Cao
Secret-key cryptography

With the location-based services booming, the volume of spatial data inevitably explodes. In order to reduce local storage and computational overhead, users tend to outsource data and initiate queries to the cloud. However, sensitive data or queries may be compromised if cloud server has access to raw data and plaintext token. To cope with this problem, searchable encryption for geometric range is applied. Geometric range search has wide applications in many scenarios, especially the...

2020/217 (PDF) Last updated: 2020-02-21
SynFi: Automatic Synthetic Fingerprint Generation
M. Sadegh Riazi, Seyed M. Chavoshian, Farinaz Koushanfar
Applications

Authentication and identification methods based on human fingerprints are ubiquitous in several systems ranging from government organizations to consumer products. The performance and reliability of such systems directly rely on the volume of data on which they have been verified. Unfortunately, a large volume of fingerprint databases is not publicly available due to many privacy and security concerns. In this paper, we introduce a new approach to automatically generate high-fidelity...

2020/167 (PDF) Last updated: 2020-05-24
Turbo-Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning
Jinhyun So, Basak Guler, A. Salman Avestimehr
Cryptographic protocols

Federated learning is gaining significant interests as it enables model training over a large volume of data that is distributedly stored over many users, while protecting the privacy of the individual users. However, a major bottleneck in scaling federated learning to a large number of users is the overhead of secure model aggregation across many users. In fact, the overhead of state-of-the-art protocols for secure model aggregation grows quadratically with the number of users. We propose a...

2020/104 (PDF) Last updated: 2020-11-18
On the Security Goals of White-Box Cryptography
Estuardo Alpirez Bock, Alessandro Amadori, Chris Brzuska, Wil Michiels
Applications

We discuss existing and new security notions for white-box cryptography and comment on their suitability for Digital Rights Management and Mobile Payment Applications, the two prevalent use-cases of white-box cryptography. In particular, we put forward indistinguishability for white-box cryptography with hardware-binding (IND-WHW) as a new security notion that we deem central. We also discuss the security property of application-binding and explain the issues faced when defining it as a...

2019/1292 (PDF) Last updated: 2019-11-07
Mitigating Leakage in Secure Cloud-Hosted Data Structures: Volume-Hiding for Multi-Maps via Hashing
Sarvar Patel, Giuseppe Persiano, Kevin Yeo, Moti Yung
Cryptographic protocols

Volume leakage has recently been identified as a major threat to the security of cryptographic cloud-based data structures by Kellaris et al. [CCS’16] (see also the attacks in Grubbs et al. [CCS’18] and Lacharité et al. [S&P’18]). In this work, we focus on volume-hiding implementations of encrypted multi-maps as first considered by Kamara and Moataz [Eurocrypt’19]. Encrypted multi-maps consist of outsourcing the storage of a multi-map to an untrusted server, such as a cloud storage system,...

2019/1224 (PDF) Last updated: 2020-04-17
Practical Volume-Based Attacks on Encrypted Databases
Rishabh Poddar, Stephanie Wang, Jianan Lu, Raluca Ada Popa
Applications

Recent years have seen an increased interest towards strong security primitives for encrypted databases (such as oblivious protocols), that hide the access patterns of query execution, and reveal only the volume of results. However, recent work has shown that even volume leakage can enable the reconstruction of entire columns in the database. Yet, existing attacks rely on a set of assumptions that are unrealistic in practice: for example, they (i) require a...

2019/1219 (PDF) Last updated: 2019-10-21
Multi-Locking and Perfect Argument Order: Two Major Improvements of Attribute-Based Encryption~(Long Paper)
Nugier Cyrius, Adelin Remi, Migliore Vincent, Alata Eric
Implementation

Attribute Based Encryption, proposed by Sahai and Waters in 2007, is a set of promising cryptographic schemes that enable various fine grained access control on encrypted data. With a unique encryption key, a user is able to encrypt data for a very specific group of recipient that matches a set of attributes contained inside their decryption key. In current scenario where personal devices share an increasing volume of private data on the web, such encryption algorithms are more than ever a...

2019/1198 (PDF) Last updated: 2019-10-15
Encrypted Databases: New Volume Attacks against Range Queries
Zichen Gui, Oliver Johnson, Bogdan Warinschi
Applications

We present a range of novel attacks which exploit information about the volume of answers to range queries in encrypted database. Our attacks rely on a strategy which is simple yet robust and effective. We illustrate the robustness of our strategy in a number of ways. We show how i) to adapt the attack for several variations of a basic usage scenario ii) to defeat countermeasures intended to thwart the premise of our basic attack and iii) to perform partial reconstruction of secret data when...

2019/1175 (PDF) Last updated: 2019-10-10
Revisiting Leakage Abuse Attacks
Laura Blackstone, Seny Kamara, Tarik Moataz

Encrypted search algorithms (ESA) are cryptographic algorithms that support search over encrypted data. ESAs can be designed with various primitives including searchable/structured symmetric encryption (SSE/STE) and oblivious RAM (ORAM). Leakage abuse attacks attempt to recover client queries using knowledge of the client’s data. An important parameter for any leakage-abuse attack is its known-data rate; that is, the fraction of client data that must be known to the adversary. In this work,...

2019/811 (PDF) Last updated: 2019-07-14
SEAL: Attack Mitigation for Encrypted Databases via Adjustable Leakage
Ioannis Demertzis, Dimitrios Papadopoulos, Charalampos Papamanthou, Saurabh Shintre
Cryptographic protocols

Building expressive encrypted databases that can scale to large volumes of data while enjoying formal security guarantees has been one of the holy grails of security and cryptography research. Searchable Encryption (SE) is considered to be an attractive implementation choice for this goal: It naturally supports basic database queries such as point, join and range, and is very practical at the expense of well-defined leakage such as search and access pattern. Nevertheless, recent attacks have...

2019/806 (PDF) Last updated: 2019-07-14
Proxy-Mediated Searchable Encryption in SQL Databases Using Blind Indexes
Eugene Pilyankevich, Dmytro Kornieiev, Artem Storozhuk
Cryptographic protocols

Rapid advances in Internet technologies have fostered the emergence of the “software as a service” model for enterprise computing. The “Database as a Service” model provides users with the power to create, store, modify, and retrieve data from any location, as long as they have access to the Internet. As more and more datasets (including those containing private and sensitive data) are outsourced to remote / cloud storage providers, the data owner, firstly, needs to be certain of the...

2019/655 (PDF) Last updated: 2019-06-04
Visualizing size-security tradeoffs for lattice-based encryption
Daniel J. Bernstein
Public-key cryptography

There are many proposed lattice-based encryption systems. How do these systems compare in the security that they provide against known attacks, under various limits on communication volume? There are several reasons to be skeptical of graphs that claim to answer this question. Part of the problem is with the underlying data points, and part of the problem is with how the data points are converted into graphs.

2019/607 (PDF) Last updated: 2020-10-09
Improved Meet-in-the-Middle Preimage Attacks against AES Hashing Modes
Zhenzhen Bao, Lin Ding, Jian Guo, Haoyang Wang, Wenying Zhang
Secret-key cryptography

Hashing modes are ways to convert a block cipher into a hash function, and those with AES as the underlying block cipher are referred to as AES hashing modes. Sasaki in 2011, introduced the first preimage attack against AES hashing modes with the AES block cipher reduced to 7 rounds, by the method of meet-in-the-middle. In his attack, the key-schedules are not taken into account. Hence, the same attack applies to all three versions of AES. In this paper, by introducing neutral bits from the...

2019/546 (PDF) Last updated: 2024-09-16
Zero-Knowledge Proof-of-Identity: Sybil-Resistant, Anonymous Authentication on Permissionless Blockchains and Incentive Compatible, Strictly Dominant Cryptocurrencies
David Cerezo Sánchez
Cryptographic protocols

Zero-Knowledge Proof-of-Identity from trusted public certificates (e.g., national identity cards and/or ePassports; eSIM) is introduced here to permissionless blockchains in order to remove the inefficiencies of Sybil-resistant mechanisms such as Proof-of-Work (i.e., high energy and environmental costs) and Proof-of-Stake (i.e., capital hoarding and lower transaction volume). The proposed solution effectively limits the number of mining nodes a single individual would be able to run while...

2019/470 (PDF) Last updated: 2020-04-23
A Practical Approach to the Secure Computation of the Moore-Penrose Pseudoinverse over the Rationals
Niek J. Bouman, Niels de Vreede
Cryptographic protocols

Solving linear systems of equations is a universal problem. In the context of secure multiparty computation (MPC), a method to solve such systems, especially for the case in which the rank of the system is unknown and should remain private, is an important building block. We devise an efficient and data-oblivious algorithm (meaning that the algorithm's execution time and branching behavior are independent of all secrets) for solving a bounded integral linear system of unknown rank over the...

2019/265 (PDF) Last updated: 2019-03-06
TEX - A Securely Scalable Trustless Exchange
Rami Khalil, Arthur Gervais, Guillaume Felley
Cryptographic protocols

Financial exchanges are typically built out of two trusted components: a trade matching and a trade settlement system. With the advent of decentralized ledgers, that perform transactions without a trusted intermediary, so called decentralized exchanges (DEX) emerged. Some DEXs propose to off-load trade order matching to a centralized system outside the blockchain to scale, but settle each trade trustlessly as an expensive on-chain transaction. While DEX are non-custodial, their order books...

2018/1062 (PDF) Last updated: 2018-11-09
DAGsim: Simulation of DAG-based distributed ledger protocols
Manuel Zander, Tom Waite, Dominik Harz
Applications

Scalability of distributed ledgers is a key adoption factor. As an alternative to blockchain-based protocols, directed acyclic graph (DAG) protocols are proposed with the intention to allow a higher volume of transactions to be processed. However, there is still limited understanding of the behaviour and security considerations of DAG-based systems. We present an asynchronous, continuous time, and multi-agent simulation framework for DAG-based cryptocurrencies. We model honest and...

2018/1045 (PDF) Last updated: 2019-01-13
MPC Joins the Dark Side
John Cartlidge, Nigel P. Smart, Younes Talibi Alaoui
Cryptographic protocols

We consider the issue of securing dark pools/markets in the financial services sector. These markets currently are executed via trusted third parties, leading to potential fraud being able to be conducted by the market operators. We present a potential solution to this problem by using Multi-Party Computation to enable a trusted third party to be emulated in software. Our experiments show that whilst the standard market clearing mechanism of Continuous Double Auction in lit markets is not...

2018/978 (PDF) Last updated: 2018-10-15
Encrypted Multi-Maps with Computationally-Secure Leakage
Seny Kamara, Tarik Moataz

We initiate the study of structured encryption schemes with computationally-secure leakage. Specifically, we focus on the design of volume-hiding encrypted multi-maps; that is, of encrypted multi-maps that hide the response length to computationally-bounded adversaries. We describe the first volume-hiding STE schemes that do not rely on naive padding; that is, padding all tuples to the same length. Our first construction has efficient query complexity and storage but can be lossy. We...

2018/965 (PDF) Last updated: 2018-10-14
Pump up the Volume: Practical Database Reconstruction from Volume Leakage on Range Queries
Paul Grubbs, Marie-Sarah Lacharité, Brice Minaud, Kenny Paterson
Applications

We present attacks that use only the volume of responses to range queries to reconstruct databases. Our focus is on practical attacks that work for large-scale databases with many values and records, without requiring assumptions on the data or query distributions. Our work improves on the previous state-of-the-art due to Kellaris \emph{et al.} (CCS 2016) in all of these dimensions. Our main attack targets reconstruction of database counts and involves a novel graph-theoretic approach. It...

2018/454 (PDF) Last updated: 2018-05-21
R3C3: Cryptographically secure Censorship Resistant Rendezvous using Cryptocurrencies
Mohsen Minaei, Pedro Moreno-Sanchez, Aniket Kate
Cryptographic protocols

Cryptocurrencies and blockchains are set to play a major role in the financial and supply-chain systems. Their presence and acceptance across different geopolitical corridors, including in repressive regimes, have been one of their striking features. In this work, we leverage this popularity for bootstrapping censorship resistant (CR) communication. We formalize the notion of stego-bootstrapping scheme and formally describe the security notions of the scheme in terms of rareness and security...

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.