International Association
for Cryptologic Research

Time-lock puzzles are unique cryptographic primitives that use computational complexity to keep information secret for some period of time, after which security expires. Unfortunately, current analysis techniques of time-lock primitives provide no sound mechanism to build multi-party cryptographic protocols which use expiring security as a building block. We explain in this paper that all other attempts at this subtle problem lack either composability, a fully consistent analysis, or functionality. The subtle flaws in the existing frameworks reduce to an impossibility by Mahmoody et al., who showed that time-lock puzzles with super-polynomial gaps (between committer and solver) cannot be constructed from random oracles alone; yet still the analyses of algebraic puzzles today treat the solving process as if each step is a generic or random oracle.

This paper presents a new complexity theoretic based framework and new structural theorems to analyze timed primitives with full generality and in composition (which is the central modular protocol design tool). The framework includes a model of security based on fine-grained circuit complexity which we call residual complexity, which accounts for possible leakage on timed primitives as they expire. Our definitions for multi-party computation protocols generalize the literature standards by accounting for fine-grained polynomial circuit depth to model computational hardness which expires in feasible time. Our composition theorems incur degradation of (fine-grained) security as items are composed. In our framework, simulators are given a polynomial “budget” for how much time they spend, and in composition these polynomials interact.

Finally, we demonstrate via a prototypical auction application how to apply our framework and theorems. For the first time, we show that it is possible to prove – in a way that is fully consistent, with falsifiable assumptions – properties of multi-party applications based on leaky, temporarily secure components.

Introduced by Kohlweiss, Lysyanskaya, and Nguyen (Eurocrypt'23), an $f$-privacy-preserving blueprint (PPB) system allows an auditor with secret input $x$ to create a public encoding of the function $f(x,\cdot)$ that verifiably corresponds to a commitment $C_x$ to $x$. The auditor will then be able to derive $f(x,y)$ from an escrow $Z$ computed by a user on input the user's private data $y$ corresponding to a commitment $C_y$. $Z$ verifiably corresponds to the commitment $C_y$ and reveals no other information about $y$. PPBs provide an abuse-resistant escrow mechanism: for example, if $f$ is the watchlist function where $f(x,y)$ outputs $y$ only in the event that $y$ is on the list $x$, then an $f$-PPB allows the auditor to trace watchlisted users in an otherwise anonymous system. Yet, the auditor's $x$ must correspond to a publicly available (and potentially authorized by a transparent, lawful process) $C_x$, and the auditor will learn nothing except $f(x,y)$. In this paper, we build on the original PPB results in three ways: (1) We define and satisfy a stronger notion of security where a malicious auditor cannot frame a user in a transaction to which this user was not a party. (2) We provide efficient schemes for a bigger class of functions $f$; for example, for the first time, we show how to realize $f$ that would allow the auditor to trace e-cash transactions of a criminal suspect. (3) For the watchlist and related functions, we reduce the size of the escrow $Z$ from linear in the size of the auditor's input $x$, to logarithmic.

Foreign field arithmetic often creates significant additional overheads in zero-knowledge proof circuits. Previous work has offloaded foreign arithmetic from proof circuits by using effective and often simple primitives such as Sigma protocols. While these successfully move the foreign field work outside of the circuit, the costs for the Sigma protocol’s verifier still remains high. In use cases where the verifier is constrained computationally this poses a major challenge. One such use case would be in proof composition where foreign arithmetic causes a blowup in the costs for the verifier circuit. In this work we show that by using folding scheme with Sigmabus and other such uniform verifier offloading techniques, we can remove foreign field arithmetic from zero-knowledge proof circuits while achieving succinct final verification. We do this by applying prior techniques iteratively and accumulate the resulting verifier work into one folding proof of size O(|F|) group elements, where F is the size of a single Sigma verifier’s computation. Then by using an existing zkSNARK we can further compress to a proof size of O(log |F|) which can be checked succinctly by a computationally constrained verifier.

The TFHE cryptosystem only supports small plaintext space, up to 5 bits with usual parameters. However, one solution to circumvent this limitation is to decompose input messages into a basis B over multiple ciphertexts. In this work, we introduce B-gates, an extension of logic gates to non binary bases, to compute base B logic circuit. The flexibility introduced by our approach improves the speed performance over previous approaches such as the so called tree-based method which requires an exponential amount of operations in the number of inputs. We provide experimental results using sorting as a benchmark application and, additionally, we obtain a speed-up of ×3 in latency compared to state of the art BGV techniques for this application. As an additional result, we introduce a keyswitching key specific to packing TLWE ciphertexts into TRLWE ciphertexts with redundancy, which is of interest in many functional bootstrapping scenarios.

In this paper, we consider two critical aspects of security in the distributed computing (DC) model: secure data shuffling and secure coded computing. It is imperative that any external entity overhearing the transmissions does not gain any information about the intermediate values (IVs) exchanged during the shuffling phase of the DC model. Our approach ensures IV confidentiality during data shuffling. Moreover, each node in the system must be able to recover the IVs necessary for computing its output functions but must also remain oblivious to the IVs associated with output functions not assigned to it. We design secure DC methods and establish achievable limits on the tradeoffs between the communication and computation loads to contribute to the advancement of secure data processing in distributed systems.

Vertical Federated Learning (VFL) is becoming a standard collaborative learning paradigm with various practical applications. Randomness is essential to enhancing privacy in VFL, but introducing too much external randomness often leads to an intolerable performance loss. Instead, as it was demonstrated for other federated learning settings, leveraging internal randomness —as provided by variational autoencoders (VAEs) —can be beneficial. However, the resulting privacy has never been quantified so far nor has the approach been investigated for VFL. We therefore propose a novel differential privacy estimate, denoted as distance-based empirical local differential privacy (dELDP). It allows to empirically bound DP parameters of concrete components, quantifying the internal randomness with appropriate distance and sensitivity metrics. We apply dELDP to investigate the DP of VAEs and observe values up to ε ≈ 6.4 and δ = 2−32. Moreover, to link the dELDP parameters to the privacy of full VAE-including VFL systems in practice, we conduct comprehensive experiments on the robustness against state-of-the-art privacy attacks. The results illustrate that the VAE system is effective against feature reconstruction attacks and outperforms other privacy-enhancing methods for VFL, especially when the adversary holds 75% of features in label inference attack.

This paper endeavors to securely implement a Physical Unclonable Function (PUF) for private data generation within Field-Programmable Gate Arrays (FPGAs). SRAM PUFs are commonly utilized due to their use of memory devices for generating secret data, particularly in resource constrained devices. However, their reliance on memory access poses side-channel threats such as data remanence decay and memory-based attacks, and the time required to generate secret data is significant. To address these issues, we propose implementing n cross-coupled inverters in Verilog to generate n secret bits, followed by syndrome for error correction hardcoded in the hardware itself. This approach improves side channel security and reduces time consumption, albeit at the expense of additional area utilization

Event date: 18 October to 19 October 2024
Submission deadline: 15 July 2024
Notification: 15 August 2024

Xiamen University Malaysia is now seeking highly motivated, committed and qualified individuals for academic teaching positions in computer science and cyber security.

Candidates in computer science and cyber security are welcome to apply. The ideal candidate is expected to be able to support general computing subjects, as well as cyber security specialization subjects. Applicants must possess a PhD degree in a related discipline.

Applicants with specific teaching and research interests in TWO OR MORE of the following areas are encouraged to apply:

• Digital Forensics and Investigation
• Network Traffic Monitoring and Analysis
• Advanced Network Attack and Defence Technology
• Malware Analysis
• Cryptanalysis
• Biometrics
• Blockchain Technology

HOW TO APPLY
Applicants are invited to submit a digital application packet to: recruit_academic@xmu.edu.my and iftekhar.salam@xmu.edu.my

The subject line of your email must include: your name, relevant academic discipline, and the specific position for which you are applying for. All application packets must include the following attachments:

1. Your detailed and current CV with publication (*Asterisk to indicate corresponding author, include Indexing & Quartile);
2. Cover letter;
3. List of courses from the above that the candidate can support;
4. Evidence of academic qualifications (Bachelor, Master & PhD Certificate; Bachelor, Master & PhD Transcripts and Professional Certificates);
5. 3-5 Full-Text publications (if applicable);
6. Teaching evaluation (if applicable);
7. Two academic references (at least one of them is the applicant’s current/most recent employer).

The positions will remain open until filled, but priority will be given to applications received by 23rd May 2024.

Closing date for applications:

Contact: iftekhar.salam@xmu.edu.my

Event date: 24 September to 26 September 2024
Submission deadline: 15 May 2024
Notification: 30 June 2024

Event date: 31 May 2024

Event date: 16 October to 17 October 2024
Submission deadline: 15 June 2024
Notification: 14 August 2024

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 the privacy of transactions in the mempool is an important goal.

In this work we focus on achieving mempool transaction privacy through a new primitive that we term batched-threshold encryption, which is a variant of threshold encryption with strict efficiency requirements to better model the needs of resource constrained environments such as blockchains. Unlike the naive use of threshold encryption, which requires communication proportional to $O(nB)$ to decrypt $B$ transactions with a committee of $n$ parties, our batched-threshold encryption scheme only needs $O(n)$ communication. We additionally discuss pitfalls in prior approaches that use (vanilla) threshold encryption for mempool privacy.

To show that our scheme is concretely efficient, we implement our scheme and find that transactions can be encrypted in under 6 ms, independent of committee size, and the communication required to decrypt an entire batch of $B$ transactions is 80 bytes per party, independent of the number of transactions $B$, making it an attractive choice when communication is very expensive. If deployed on Ethereum, which processes close to 500 transaction per block, it takes close to 2.8 s for each committee member to compute a partial decryption and under 3.5 s to decrypt all transactions for a block in single-threaded mode.

This paper studies the optimal transaction fee mechanisms for blockchains, focusing on the distinction between price-based ($\mathcal{P}$) and quantity-based ($\mathcal{Q}$) controls. By analyzing factors such as demand uncertainty, validator costs, cryptocurrency price fluctuations, price elasticity of demand, and levels of decentralization, we establish criteria that determine the selection of transaction fee mechanisms. We present a model framed around a Nash bargaining game, exploring how blockchain designers and validators negotiate fee structures to balance network welfare with profitability. Our findings suggest that the choice between $\mathcal{P}$ and $\mathcal{Q}$ mechanisms depends critically on the blockchain’s specific technical and economic features. The study concludes that no single mechanism suits all contexts and highlights the potential for hybrid approaches that adaptively combine features of both $\mathcal{P}$ and $\mathcal{Q}$ to meet varying demands and market conditions.

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 obsolete as attacks become more sophisticated, "crypto-agility" -– the ability to swiftly replace ciphers – represents the key challenge to deployment of software like ours. Partitioning is a crucial method for establishing such agility, as it enables the replacement of compromised software without affecting software on other partitions, greatly simplifying the certification process necessary in an avionics environment.

Our performance measurements constitute initial evidence that both the memory and performance characteristics of this approach are suitable for deployment in flight-computers currently in use. Prior to optimisation, performance measurements show a modest memory requirement of under 400 KB of RAM, but employ a more substantial stack usage of just under 200 KB. Our most advanced redundant post-quantum cipher is five times slower than its non-redundant, pre-quantum counterpart.

We present Whisper, a system for privacy-preserving collection of aggregate statistics. Like prior systems, a Whisper deployment consists of a small set of non-colluding servers; these servers compute aggregate statistics over data from a large number of users without learning the data of any individual user. Whisper’s main contribution is that its server- to-server communication cost and its server-side storage costs scale sublinearly with the total number of users. In particular, prior systems required the servers to exchange a few bits of information to verify the well-formedness of each client submission. In contrast, Whisper uses silently verifiable proofs, a new type of proof system on secret-shared data that allows the servers to verify an arbitrarily large batch of proofs by exchanging a single 128-bit string. This improvement comes with increased client-to-server communication, which, in cloud computing, is typically cheaper (or even free) than the cost of egress for server-to-server communication. To reduce server storage, Whisper approximates certain statistics using small-space sketching data structures. Applying randomized sketches in an environment with adversarial clients requires a careful and novel security analysis. In a deployment with two servers and 100,000 clients of which 1% are malicious, Whisper can improve server-to-server communication for vector sum by three orders of magnitude while each client’s communication increases by only 10%.

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. In the homomorphic PRF evaluation setting, given a fully homomorphic encryption of the PRF secret key $\vec{s}$, it should be possible to homomorphically compute encryptions of PRF evaluations $\{ \text{PRF}_{\vec{s}}(x_i) \}_{i=1}^M$ for public inputs $\{ x_i\}_{i=1}^M$. We consider this problem for PRF families based on the hardness of the Learning-With-Rounding (LWR) problem introduced by Banerjee, Peikert and Rosen (Eurocrypt '12). We build on the random-oracle variant of a PRF construction suggested by Banerjee et al. and demonstrate that it can be evaluated using only two sequential programmable bootstraps in the TFHE homomorphic encryption scheme. We also describe several modifications of this PRF---which we prove as secure as the original function---that support homomorphic evaluations using only one programmable bootstrap per slot.

Numerical experiments were conducted using practically relevant FHE parameter sets from the TFHE-rs library. Our benchmarks show that a throughput of about $1000$ encrypted pseudorandom bits per second (resp. $900$ encrypted pseudorandom bits per second) can be achieved on an AWS hpc7a.96xlarge machine (resp. on a standard laptop with an Apple M2 chip), on a single thread. The PRF evaluation keys in our experiments have sizes roughly $40\%$ and $60\%$ of a bootstrapping key. Applying our solution to transciphering enables important bandwidth savings, typically trading $64$-bit values for $4$-bit values per transmitted ciphertext.

Byzantine fault-tolerant (BFT) protocols are known to suffer from the scalability issue. Indeed, their performance degrades drastically as the number of replicas $n$ grows. While a long line of work has attempted to achieve the scalability goal, these works can only scale to roughly a hundred replicas.

In this paper, we develop BFT protocols from the so-called committee sampling approach that selects a small committee for consensus and conveys the results to all replicas. Such an approach, however, has been focused on the Byzantine agreement (BA) problem (considering replicas only) instead of the BFT problem (in the client-replica model); also, the approach is mainly of theoretical interest only, as concretely, it works for impractically large $n$.

We build an extremely efficient, scalable, and adaptively secure BFT protocol called Pando in partially synchronous environments based on the committee sampling approach. In particular, we devise novel BFT building blocks targeting scalability, including communication-efficient and computation-efficient consistent broadcast and atomic broadcast protocols.

Pando inherits some inherent issues of committee sampling-based protocols: Pando can only achieve near-optimal resilience (i.e., $f<(1/3-\epsilon)n$, where $f$ is the number of faulty replicas and $\epsilon$ is a small constant), and Pando attains safety and liveness only probabilistically. Interestingly, to make $\epsilon$ come close to 0 (near-optimal resilience), $n$ needs to be sufficiently large but not impractically large, e.g., $n>500$---just what we need for scalable BFT.

Our evaluation on Amazon EC2 shows that in contrast to existing protocols, Pando can easily scale to a thousand replicas in the WAN environment, achieving a throughput of 62.57 ktx/sec.

Vector Commitment (VC) enables one to commit to a vector, and then the element at a specific position can be opened, with proof of consistency to the initial commitment. VC is a powerful primitive with various applications, including stateless cryptocurrencies. Recently, matrix commitment Matproofs (Liu and Zhang CCS 2022), as an extension of VC, has been proposed to reduce the communication and computation complexity of VC-based cryptocurrencies. However, Matproofs requires linear-sized public parameters, and the aggregated proof size may also increase linearly with the number of individual proofs aggregated. Additionally, the proof updating process involves the third party, known as Proof-Serving Nodes (PSNs), which leads to extra storage and communication overhead. In this paper, we first propose a multi-dimensional variant of matrix commitment and construct a new matrix commitment scheme for two-dimensional matrix, called 2D-Xproofs, which achieves optimal aggregated proof size without using PSNs. Furthermore, we present a highly maintainable three-dimensional scheme, 3D-Xproofs, which updates all proofs within time sublinear in the size of the committed matrix without PSNs' assistance. More generally, we could further increase the matrix dimensionality to achieve more efficient proof updates. Finally, we demonstrate the security of our schemes, showing that both schemes are position binding. We also implement both schemes, and the results indicate that our schemes enjoy constant-sized aggregated proofs and sublinear-sized public parameters, and the proof update time in 3D-Xproofs is $2.5\times$ faster than Matproofs.

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 applications.

In this paper, we propose two novel non-interactive batched PDTE protocols, BPDTE_RCC and BPDTE_CW, based on two new ciphertext-plaintext comparison algorithms, the improved range cover comparison (RCC) comparator and the constant-weight (CW) piece-wise comparator, respectively. Compared to the current state-of-the-art Level Up (CCS'23), our comparison algorithms are up to $72\times$ faster for batched inputs of 16 bits. Moreover, we introduced a new tree traversal method called Adapted SumPath, to achieve $\mathcal{O}(1)$ complexity of the server's response, whereas Level Up has $\mathcal{O}(2^d)$ for a depth-$d$ tree where the client needs to look up classification values in a table. Overall, our PDTE protocols attain the optimal server-to-client communication complexity and are up to $17\times$ faster than Level Up in batch size 16384.