[digest] 2024 Week 26

## In this issue

1. [2024/356] On Central Primitives for Quantum Cryptography with ...
2. [2024/548] Efficient isochronous fixed-weight sampling with ...
3. [2024/753] Summation-based Private Segmented Membership Test ...
4. [2024/759] Watermarking Language Models for Many Adaptive Users
5. [2024/1014] Grafting: Complementing RNS in CKKS
6. [2024/1015] Expediting Homomorphic Computation via ...
7. [2024/1016] A Succinct Range Proof for Polynomial-based Vector ...
8. [2024/1017] Accelerating pairings on BW10 and BW14 Curves
9. [2024/1018] Sparsity-Aware Protocol for ZK-friendly ML Models: ...
10. [2024/1019] Exploiting Clock-Slew Dependent Variability in CMOS ...
11. [2024/1020] chainBoost: A Secure Performance Booster for ...
12. [2024/1021] ammBoost: State Growth Control for AMMs
13. [2024/1022] Competitive Policies for Online Collateral Maintenance
14. [2024/1023] Constant-Size Unbounded Multi-Hop Fully Homomorphic ...
15. [2024/1024] Attribute-Based Threshold Issuance Anonymous ...
16. [2024/1025] Polynomial sharings on two secrets: Buy one, get ...
17. [2024/1026] MaSTer: Maliciously Secure Truncation for ...
18. [2024/1027] Structured-Seed Local Pseudorandom Generators and ...
19. [2024/1028] FASIL: A challenge-based framework for secure and ...
20. [2024/1029] Oblivious Single Access Machines: A New Model for ...
21. [2024/1030] GRASP: Accelerating Hash-based PQC Performance on ...
22. [2024/1031] SACfe: Secure Access Control in Functional ...
23. [2024/1032] Threshold OPRF from Threshold Additive HE
24. [2024/1033] Adaptively Secure 5 Round Threshold Signatures from ...
25. [2024/1034] A Practical Protocol for Quantum Oblivious Transfer ...
26. [2024/1035] Reading It like an Open Book: Single-trace Blind ...
27. [2024/1036] A note on the G-FFT
28. [2024/1037] A note on adding zero-knowledge to STARKs
29. [2024/1038] Constraint-Packing and the Sum-Check Protocol over ...
30. [2024/1039] Reduction from Average-Case M-ISIS to Worst-Case ...
31. [2024/1040] PeaceFounder: centralised E2E verifiable evoting ...
32. [2024/1041] Embedding Integer Lattices as Ideals into ...
33. [2024/1042] Efficient Verifiable Differential Privacy with ...
34. [2024/1043] Cryptography in the Common Haar State Model: ...
35. [2024/1044] Searching for differential addition chains
36. [2024/1045] Efficient Secret Sharing for Large-Scale Applications
37. [2024/1046] The Sum-Check Protocol over Fields of Small ...
38. [2024/1047] Improved Multi-Party Fixed-Point Multiplication
39. [2024/1048] Distributional Secure Merge
40. [2024/1049] KyberSlash: Exploiting secret-dependent division ...
41. [2024/1050] On Sequential Functions and Fine-Grained Cryptography
42. [2024/1051] Adaptor Signatures: New Security Definition and A ...
43. [2024/1052] A New Fine Tuning Method for FHEW/TFHE ...
44. [2024/1053] Stochastic Secret Sharing with $1$-Bit Shares and ...
45. [2024/1054] Optimized Computation of the Jacobi Symbol
46. [2024/1055] Enhancing Local Verification: Aggregate and Multi- ...
47. [2024/1056] Shuffle Arguments Based on Subset-Checking
48. [2024/1057] Password-authenticated Key Exchange and Applications
49. [2024/1058] Natively Compatible Super-Efficient Lookup ...
50. [2024/1059] HEProfiler: An In-Depth Profiler of Approximate ...
51. [2024/1060] Quirky Interactive Reductions of Knowledge
52. [2024/1061] Insta-Pok3r: Real-time Poker on Blockchain
53. [2024/1062] Compact Key Function Secret Sharing with Non-linear ...
54. [2024/1063] VIMz: Verifiable Image Manipulation using Folding- ...
55. [2024/1064] ArcEDB: An Arbitrary-Precision Encrypted Database ...
56. [2024/1065] AITIA: Efficient Secure Computation of Bivariate ...

## 2024/356

* Title: On Central Primitives for Quantum Cryptography with Classical Communication
* Authors: Kai-Min Chung, Eli Goldin, Matthew Gray
* [Permalink](https://eprint.iacr.org/2024/356)
* [Download](https://eprint.iacr.org/2024/356.pdf)

### Abstract

Recent work has introduced the "Quantum-Computation Classical-Communication"
(QCCC) (Chung et. al.) setting for cryptography. There has been some evidence that
One Way Puzzles (OWPuzz) are the natural central cryptographic primitive for this
setting (Khurana and Tomer). For a primitive to be considered central it should
have several characteristics. It should be well behaved (which for this paper we will
think of as having amplification, combiners, and universal constructions); it should
be implied by a wide variety of other primitives; and it should be equivalent to some
class of useful primitives. We present combiners, correctness and security amplifica-
tion, and a universal construction for OWPuzz. Our proof of security amplification
uses a new and cleaner version construction of EFI from OWPuzz (in comparison to
the result of Khurana and Tomer) that generalizes to weak OWPuzz and is the most
technically involved section of the paper. It was previously known that OWPuzz are
implied by other primitives of interest including commitments, symmetric key encryp-
tion, one way state generators (OWSG), and therefore pseudorandom states (PRS).
However we are able to rule out OWPuzz’s equivalence to many of these primitives
by showing a black box separation between general OWPuzz and a restricted class
of OWPuzz (those with efficient verification, which we call EV − OWPuzz). We then
show that EV − OWPuzz are also implied by most of these primitives, which separates
them from OWPuzz as well. This separation also separates extending PRS from highly
compressing PRS answering an open question of Ananth et. al.



## 2024/548

* Title: Efficient isochronous fixed-weight sampling with applications to NTRU
* Authors: Décio Luiz Gazzoni Filho, Tomás S. R. Silva, Julio López
* [Permalink](https://eprint.iacr.org/2024/548)
* [Download](https://eprint.iacr.org/2024/548.pdf)

### Abstract

We present a solution to the open problem of designing a linear-time, unbiased and timing attack-resistant shuffling algorithm for fixed-weight sampling. Although it can be implemented without timing leakages of secret data in any architecture, we illustrate with ARMv7-M and ARMv8-A implementations; for the latter, we take advantage of architectural features such as NEON and conditional instructions, which are representative of features available on architectures targeting similar systems, such as Intel. Our proposed algorithm improves asymptotically upon the current approach based on constant-time sorting networks ($O(n)$ versus $O(n \log^2 n)$), and an implementation of the new algorithm applied to NTRU is also faster in practice, by a factor of up to $6.91\ (591\%)$ on ARMv8-A cores and $12.89\ (1189\%)$ on the Cortex-M4; it also requires fewer uniform random bits. This translates into performance improvements for NTRU encapsulation, compared to state-of-the-art implementations, of up to 50\% on ARMv8-A cores and 72\% on the Cortex-M4, and small improvements to key generation (up to 2.7\% on ARMv8-A cores and 6.1\% on the Cortex-M4), with negligible impact on code size and a slight improvement in RAM usage for the Cortex-M4.



## 2024/753

* Title: Summation-based Private Segmented Membership Test from Threshold-Fully Homomorphic Encryption
* Authors: Nirajan Koirala, Jonathan Takeshita, Jeremy Stevens, Taeho Jung
* [Permalink](https://eprint.iacr.org/2024/753)
* [Download](https://eprint.iacr.org/2024/753.pdf)

### Abstract

In many real-world scenarios, there are cases where a client wishes
to check if a data element they hold is included in a set segmented
across a large number of data holders. To protect user privacy, the
client’s query and the data holders’ sets should remain encrypted
throughout the whole process. Prior work on Private Set Intersection (PSI), Multi-Party PSI (MPSI), Private Membership Test (PMT),
and Oblivious RAM (ORAM) falls short in this scenario in many
ways. They either require data holders to possess the sets in plain-
text, incur prohibitively high latency for aggregating results from a
large number of data holders, leak the information about the party
holding the intersection element, or induce a high false positive.
This paper introduces the primitive of a Private Segmented Mem-
bership Test (PSMT). We give a basic construction of a protocol to
solve PSMT using a threshold variant of approximate-arithmetic
homomorphic encryption and show how to overcome existing
challenges to construct a PSMT protocol without leaking information about the party holding the intersection element or false
positives for a large number of data holders ensuring IND-CPA^𝐷
security. Our novel approach is superior to existing state-of-the-art
approaches in scalability with regard to the number of supported
data holders. This is enabled by a novel summation-based homo-
morphic membership check rather than a product-based one, as
well as various novel ideas addressing technical challenges. Our
PSMT protocol supports many more parties (up to 4096 in experiments) compared to prior related work that supports only around
100 parties efficiently. Our experimental evaluation shows that our
method’s aggregation of results from data holders can run in 92.5s
for 1024 data holders and a set size of 2^25, and our method’s over-
head increases very slowly with the increasing number of senders.
We also compare our PSMT protocol to other state-of-the-art PSI
and MPSI protocols and discuss our improvements in usability with
a better privacy model and a larger number of parties



## 2024/759

* Title: Watermarking Language Models for Many Adaptive Users
* Authors: Aloni Cohen, Alexander Hoover, Gabe Schoenbach
* [Permalink](https://eprint.iacr.org/2024/759)
* [Download](https://eprint.iacr.org/2024/759.pdf)

### Abstract

We study watermarking schemes for language models with provable guarantees. As we show, prior works offer no robustness guarantees against adaptive prompting: when a user queries a language model more than once, as even benign users do. And with just a single exception (Christ and Gunn, 2024), prior works are restricted to zero-bit watermarking:  machine-generated text can be detected as such, but no additional information can be extracted from the watermark.. Unfortunately, merely detecting AI-generated text may not prevent future abuses.

We introduce multi-user watermarks, which allow tracing model-generated text to individual users or to groups of colluding users, even in the face of adaptive prompting. We construct multi-user watermarking schemes from undetectable, adaptively robust, zero-bit watermarking schemes (and prove that the undetectable zero-bit scheme of Christ, Gunn, and Zamir (2024) is adaptively robust). Importantly, our scheme provides both zero-bit and multi-user assurances at the same time. It detects shorter snippets just as well as the original scheme, and traces longer excerpts to individuals.

The main technical component is a construction of message-embedding watermarks from zero-bit watermarks. Ours is the first generic reduction between watermarking schemes for language models.  A challenge for such reductions is the lack of a unified abstraction for robustness --- that marked text is detectable even after edits. We introduce a new unifying abstraction called AEB-robustness. AEB-robustness provides that the watermark is detectable whenever the edited text "approximates enough blocks" of model-generated output.



## 2024/1014

* Title: Grafting: Complementing RNS in CKKS
* Authors: Jung Hee Cheon, Hyeongmin Choe, Minsik Kang, Jaehyung Kim
* [Permalink](https://eprint.iacr.org/2024/1014)
* [Download](https://eprint.iacr.org/2024/1014.pdf)

### Abstract

The RNS variant of the CKKS scheme (SAC 2018) is widely implemented due to its computational efficiency. However, the current optimized implementations of the RNS-CKKS scheme have a limitation when choosing the ciphertext modulus. It requires the scale factors to be approximately equal to a factor (or a product of factors) of the ciphertext modulus. This restriction causes inefficiency when the scale factor is not close to the power of the machine's word size, wasting the machine's computation budget.

In this paper, we solve this implementation-side issue algorithmically by introducing \emph{Grafting}, a ciphertext modulus management system. In Grafting, we mitigate the link between the ciphertext modulus and the application-dependent scale factor. We efficiently enable rescaling by an arbitrary amount of bits by suggesting a method managing the ciphertext modulus with mostly word-sized factors. Thus, we can fully utilize the machine architecture with word-sized factors of the ciphertext modulus while keeping the application-dependent scale factors. This also leads to hardware-friendly RNS-CKKS implementation as a side effect. Furthermore, we apply our technique to Tuple-CKKS multiplication (CCS 2023), solving a restriction due to small scale factors.

Our proof-of-concept implementation shows that the overall complexity of RNS-CKKS is almost proportional to the number of coprime factors comprising the ciphertext modulus, of size smaller than the machine's word size. This results in a substantial speed-up from Grafting: $17$-$51$% faster homomorphic multiplications and $43$% faster CoeffsToSlots in bootstrapping, implemented based on the HEaaN library. We estimate that the computational gain could range up to $1.71\times$ speed-up for the current parameters used in the RNS-CKKS libraries.



## 2024/1015

* Title: Expediting Homomorphic Computation via Multiplicative Complexity-aware Multiplicative Depth Minimization
* Authors: Mingfei Yu, Giovanni De Micheli
* [Permalink](https://eprint.iacr.org/2024/1015)
* [Download](https://eprint.iacr.org/2024/1015.pdf)

### Abstract

Fully homomorphic encryption (FHE) enables secure data processing without compromising data access, but its computational cost and slower execution compared to plaintext operations pose challenges. The growing interest in FHE-based secure computation necessitates the acceleration of homomorphic computations.. While existing research primarily targets the reduction of the multiplicative depth (MD) of homomorphic circuits, this paper addresses the trade-off between MD reduction and the increase in multiplicative complexity (MC), a critical gap often overlooked during circuit optimization and potentially resulting in suboptimal outcomes. Three contributions are presented: (a) an exact synthesis paradigm for optimal homomorphic circuit implementations, (b) an efficient heuristic algorithm named MC-aware MD minimization, and (c) a homomorphic circuit optimization flow combining MC-aware MD minimization with existing MD reduction techniques. Experimental results demonstrate a 21.32% average reduction in homomorphic computation time and showcase significantly improved efficiency in circuit optimization.



## 2024/1016

* Title: A Succinct Range Proof for Polynomial-based Vector Commitment
* Authors: Rui Gao, Zhiguo Wan, Yuncong Hu, Huaqun Wang
* [Permalink](https://eprint.iacr.org/2024/1016)
* [Download](https://eprint.iacr.org/2024/1016.pdf)

### Abstract

A range proof serves as a protocol for the prover to prove to the verifier that a committed number lies in a specified range, such as $[0,2^n)$, without disclosing the actual value. Range proofs find extensive application in various domains. However, the efficiency of many existing schemes diminishes significantly when confronted with batch proofs encompassing multiple elements.
  To improve the scalability and efficiency, we propose MissileProof, a vector range proof scheme, proving that every element in the committed vector is within $[0,2^n)$. We first reduce this argument to a bi-to-univariate SumCheck problem and a bivariate polynomial ZeroTest problem. Then generalizing the idea of univariate SumCheck PIOP, we design a bi-to-univariate SumCheck PIOP. By introducing a random polynomial, we construct the bivariate polynomial ZeroTest using a univariate polynomial ZeroTest and a univariate polynomial SumCheck PIOP. Finally, combining the PIOP for vector range proof, a KZG-based polynomial commitment scheme and the Fiat-Shamir transformation, we get a zero-knowledge succinct non-interactive vector range proof.
  Compared with existing schemes, our scheme has the optimal proof size ($O(1)$), the optimal commitment length ($O(1)$),
  and the optimal verification time ($O(1)$), at the expense of slightly sacrificing proof time ($O(l\log l\cdot n\log n)$ operations on the prime field for FFT and $O(ln)$ group exponentiations in $\mathbb{G}$). Moreover, we implemented an anti-money-laundering stateless blockchain based on the MissileProof. The gas consumption of the verification smart contract is reduced by 85%.



## 2024/1017

* Title: Accelerating pairings on BW10 and BW14 Curves
* Authors: Senegue Gomez Nyamsi, Laurian Guimagang Azebaze, Emmanuel Fouotsa
* [Permalink](https://eprint.iacr.org/2024/1017)
* [Download](https://eprint.iacr.org/2024/1017.pdf)

### Abstract

Since the advent of pairing based cryptography, many researchers have developed several techniques and variants of pairings to optimise the speed of pairing computations. The selection of the elliptic curve for a given pairing based protocol is crucial for operations in the first and second pairing groups of points of the elliptic curve and for many cryptographic schemes. A new variant of superoptimal pairing was proposed in 2023, namely x-superoptimal pairing on curves with odd prime embedding degrees BW13-310 and BW19-286. This paper extends the definition of the x-superoptimal pairing on elliptic curves with even embedding degrees BW10-511 and BW14-351 at 128 bits security level. We provide a suitable formula of the x-superoptimal pairing on BW10-511 and BW14-351 where the Miller loop is about $13.5\%$ and $21.6\%$ faster than the optimal ate pairing on BW10-511 and BW14-351 respectively. The correctness of the x-superoptimal pairing on BW10-511 and BW14-351 and bilinearity has been verified by a Magma code.



## 2024/1018

* Title: Sparsity-Aware Protocol for ZK-friendly ML Models: Shedding Lights on Practical ZKML
* Authors: Alan Li, Qingkai Liang, Mo Dong
* [Permalink](https://eprint.iacr.org/2024/1018)
* [Download](https://eprint.iacr.org/2024/1018.pdf)

### Abstract

As deep learning is being widely adopted across various domains, ensuring the integrity of models has become increasingly crucial. Despite the recent advances in Zero-Knowledge Machine Learning (ZKML) techniques, proving the inference over large ML models is still prohibitive. To enable practical ZKML, model simplification techniques like pruning and quantization should be applied without hesitation. Contrary to conventional belief, recent development in ML space have demonstrated that these simplification techniques not only condense complex models into forms with sparse, low-bit weight matrices, but also maintain exceptionally high model accuracies that matches its unsimplified counterparts.

While such transformed models seem inherently ZK-friendly, directly applying existing ZK proof frameworks still lead to suboptimal inference proving performance. To make ZKML truly practical, a quantization-and-pruning-aware ZKML framework is needed. In this paper, we propose SpaGKR, a novel sparsity-aware ZKML framework that is proven to surpass capabilities of existing ZKML methods. SpaGKR is a general framework that is widely applicable to any computation structure where sparsity arises. It is designed to be modular - all existing GKR-based ZKML frameworks can be seamlessly integrated with it to get remarkable compounding performance enhancements. We tailor SpaGKR specifically to the most commonly-used neural network structure - the linear layer, and propose the SpaGKR-LS protocol that achieves asymptotically optimal prover time. Notably, when applying SpaGKR-LS to a special series of simplified model - ternary network, it achieves further efficiency gains by additionally leveraging the low-bit nature of model parameters.



## 2024/1019

* Title: Exploiting Clock-Slew Dependent Variability in CMOS Digital Circuits Towards Power and EM SCA Resilience
* Authors: Archisman Ghosh, Md. Abdur Rahman, Debayan Das, Santosh Ghosh, Shreyas Sen
* [Permalink](https://eprint.iacr.org/2024/1019)
* [Download](https://eprint.iacr.org/2024/1019.pdf)

### Abstract

Mathematically secured cryptographic implementations leak critical information in terms of power, EM emanations, etc. Several circuit-level countermeasures are proposed to hinder side channel leakage at the source. Circuit-level countermeasures (e.g., IVR, STELLAR, WDDL, etc) are often preferred as they are generic and have low overhead. They either dither the voltage randomly or attenuate the meaningful signature at $V_{DD}$ port. Although any digital implementation has two generic ports, namely clock and $V_{DD}$, circuit-level countermeasures primarily focus on $V_{DD}$ port, and countermeasures using the clock are mainly unexplored. System-level clock randomization is ineffective due to post-processing techniques. This work, for the first time, presents clock-based countermeasures by providing a controlled slew that exploits the inherent variability of digital circuits in terms of power consumption and transforms power/EM emanation into a complex function of data and slew. Due to this, minimum traces-to-disclosure (MTD) improves by 100$\times$ with respect to the unprotected one.
Moreover, the slewed clock reduces the leaky frequency, and the clock randomization countermeasure is more effective as it becomes more difficult} to post-process in the frequency domain. Clock slew and randomization together have a cumulative effect(1800x) more than the multiplication of individual techniques (100x & 5x respectively). In brief, this paper presents a clock-level generic synthesizable countermeasure technique that improved the minimum-traces-to-disclosure (MTD) by 1800$\times$ and incurs only 11% area overhead, $<3\%$ power overhead (measured) and $<6\%$ performance overhead (measured). Moreover, this can be easily combined with other power-port-based mitigation techniques for enhanced security.



## 2024/1020

* Title: chainBoost: A Secure Performance Booster for Blockchain-based Resource Markets
* Authors: Zahra Motaqy, Mohamed E. Najd, Ghada Almashaqbeh
* [Permalink](https://eprint.iacr.org/2024/1020)
* [Download](https://eprint.iacr.org/2024/1020.pdf)

### Abstract

Cryptocurrencies and blockchain technology provide an innovative model for reshaping digital services. Driven by the movement toward Web 3.0, recent systems started to provide distributed services, such as computation outsourcing or file storage, on top of the currency exchange medium. By allowing anyone to join and collect cryptocurrency payments for serving others, these systems create decentralized markets for trading digital resources. Yet, there is still a big gap between the promise of these markets and their practical viability. Existing initiatives are still early-stage and have already encountered security and efficiency obstacles. At the same time, existing work around promising ideas, specifically sidechains, fall short in exploiting their full potential in addressing these problems.

To bridge this gap, we propose chainBoost, a secure performance booster for decentralized resource markets. It expedites service related operations, reduces the blockchain size, and supports flexible service-payment exchange modalities at low overhead. At its core, chainBoost employs a sidechain, that has a (security and semantic) mutual-dependence with the mainchain, to which the system offloads heavy/frequent operations. To enable it, we develop a novel sidechain architecture composed of temporary and permanent blocks, a block suppression mechanism to prune the sidechain, a syncing protocol to permit arbitrary data exchange between the two chains, and an autorecovery protocol to support robustness and resilience. We analyze the security of chainBoost, and implement a proof-of-concept prototype for a distributed file storage market as a use case. For a market handling around 2000 transactions per round, our experiments show up to 11x improvement in throughput and 94% reduction in confirmation time. They also show that chainBoost can reduce the main blockchain size by about 90%, and that it outperforms comparable optimistic rollup solutions by reducing transaction finality by 99.7%.



## 2024/1021

* Title: ammBoost: State Growth Control for AMMs
* Authors: Nicholas Michel, Mohamed E. Najd, Ghada Almashaqbeh
* [Permalink](https://eprint.iacr.org/2024/1021)
* [Download](https://eprint.iacr.org/2024/1021.pdf)

### Abstract

Automated market makers (AMMs) are a form of decentralized cryptocurrency exchanges and considered a prime example of Decentralized Finance (DeFi) applications. Their popularity and high trading activity have resulted in millions of on-chain transactions leading to serious scalability issues. In this paper, we address the on-chain storage overhead problem of AMMs by utilizing a new sidechain architecture as a layer 2 solution, building a system called ammBoost. Our system reduces the amount of on-chain transactions, boosts throughput, and supports blockchain pruning. We devise several techniques to enable layer 2 processing for AMMs while preserving correctness and security of the underlying AMM. We also build a proof-of-concept of ammBoost for a Uniswap-inspired use case to empirically evaluate its performance. Our experiments show that ammBoost decreases the gas cost by 94.53% and the chain growth by at least 80%, and that it can support up to 500x of the daily traffic volume observed for Uniswap in practice.



## 2024/1022

* Title: Competitive Policies for Online Collateral Maintenance
* Authors: Ghada Almashaqbeh, Sixia Chen, Alexander Russell
* [Permalink](https://eprint.iacr.org/2024/1022)
* [Download](https://eprint.iacr.org/2024/1022.pdf)

### Abstract

Layer-two blockchain protocols emerged to address scalability issues related to fees, storage cost, and confirmation delay of on-chain transactions. They aggregate off-chain transactions into a fewer on-chain ones, thus offering immediate settlement and reduced transaction fees. To preserve security of the underlying ledger, layer-two protocols often work in a collateralized model; resources are committed on-chain to backup off-chain activities. A fundamental challenge that arises in this setup is determining a policy for establishing, committing, and replenishing the collateral in a way that maximizes the value of settled transactions.

In this paper, we study this problem under two settings that model collateralized layer-two protocols. The first is a general model in which a party has an on-chain collateral $C$ with a policy to decide on whether to settle or discard each incoming transaction. The policy also specifies when to replenish $C$ based on the remaining collateral value. The second model considers a discrete setup in which $C$ is divided among $k$ wallets, each of which is of size $C/k$, such that when a wallet is full, and so cannot settle any incoming transactions, it will be replenished. We devise several online policies for these models, and show how competitive they are compared to optimal (offline) policies that have full knowledge of the incoming transaction stream. To the best of our knowledge, we are the first to study and formulate online competitive policies for collateral and wallet management in the blockchain setting.



## 2024/1023

* Title: Constant-Size Unbounded Multi-Hop Fully Homomorphic Proxy Re-Encryption from Lattices
* Authors: Feixiang Zhao, Huaxiong Wang, Jian Weng
* [Permalink](https://eprint.iacr.org/2024/1023)
* [Download](https://eprint.iacr.org/2024/1023.pdf)

### Abstract

Proxy re-encryption is a cryptosystem that achieves efficient encrypted data sharing by allowing a proxy to transform a ciphertext encrypted under one key into another ciphertext under a different key. Homomorphic proxy re-encryption (HPRE) extends this concept by integrating homomorphic encryption, allowing not only the sharing of encrypted data but also the homomorphic computations on such data. The existing HPRE schemes, however, are limited to a single or bounded number of hops of ciphertext re-encryptions. To address this limitation, this paper introduces a novel lattice-based, unbounded multi-hop fully homomorphic proxy re-encryption (FHPRE) scheme, with constant-size ciphertexts. Our FHPRE scheme supports an unbounded number of reencryption operations and enables arbitrary homomorphic computations over original, re-encrypted, and evaluated ciphertexts. Additionally, we propose a potential application of our FHPRE scheme in the form of a non-interactive, constant-size multi-user computation system for cloud computing environments.



## 2024/1024

* Title: Attribute-Based Threshold Issuance Anonymous Counting Tokens and Its Application to Sybil-Resistant Self-Sovereign Identity
* Authors: Reyhaneh Rabaninejad, Behzad Abdolmaleki, Sebastian Ramacher, Daniel Slamanig, Antonis Michalas
* [Permalink](https://eprint.iacr.org/2024/1024)
* [Download](https://eprint.iacr.org/2024/1024.pdf)

### Abstract

Self-sovereign identity (SSI) systems empower users to (anonymously) establish and verify their identity when accessing both digital and real-world resources, emerging as a promising privacy-preserving solution for user-centric identity management. Recent work by Maram et al. proposes the privacy-preserving Sybil-resistant decentralized SSI system CanDID (IEEE S&P 2021). While this is an important step, notable shortcomings undermine its efficacy. The two most significant among them being the following: First, unlinkability breaks in the presence of a single malicious issuer. Second, it introduces interactiveness, as the users are required to communicate each time with issuers to collect credentials intended for use in interactions with applications. This contradicts the goal of SSI, whose aim is to give users full control over their identities. This paper first introduces the concept of publicly verifiable attribute-based threshold anonymous counting tokens (tACT). Unlike recent approaches confined to centralized settings (Benhamouda et al., ASIACRYPT 2023), tACT operates in a distributed-trust environment. Accompanied by a formal security model and a provably secure instantiation, tACT introduces a novel dimension to token issuance, which, we believe, holds independent interest. Next, the paper leverages the proposed tACT scheme to construct an efficient Sybil-resistant SSI system. This system supports various functionalities, including threshold issuance, unlinkable multi-show selective disclosure, and non-interactive, non-transferable credentials that offer constant-size credentials. Finally, our benchmark results show an efficiency improvement in our construction when compared to CanDID all while accommodating a greater number of issuers and additionally reducing to a one-round protocol that can be run in parallel with all issuers.



## 2024/1025

* Title: Polynomial sharings on two secrets: Buy one, get one free
* Authors: Paula Arnold, Sebastian Berndt, Thomas Eisenbarth, Maximilian Orlt
* [Permalink](https://eprint.iacr.org/2024/1025)
* [Download](https://eprint.iacr.org/2024/1025.pdf)

### Abstract

While passive side-channel attacks and active fault attacks have been studied intensively in the last few decades, strong attackers combining these attacks have only been studied relatively recently. Due to its simplicity, most countermeasures against passive attacks are based on additive sharing. Unfortunately, extending these countermeasures against faults often leads to quite a significant performance penalty, either due to the use of expensive cryptographic operations or a large number of shares due to massive duplication. Just recently, Berndt, Eisenbarth, Gourjon, Faust, Orlt, and Seker thus proposed to use polynomial sharing against combined attackers (CRYPTO 2023). While they construct gadgets secure against combined attackers using only a linear number of shares, the overhead introduced might still be too large for practical scenarios.

In this work, we show how the overhead of nearly all known constructions using polynomial sharing can be reduced by nearly half by embedding two secrets in the coefficients of one polynomial at the expense of increasing the degree of the polynomial by one. We present a very general framework that allows adapting these constructions to this new sharing scheme and prove the security of this approach against purely passive side-channel attacks, purely active fault attacks, and combined attacks. Furthermore, we present new gadgets allowing us to operate upon the different secrets in a number of useful ways.



## 2024/1026

* Title: MaSTer: Maliciously Secure Truncation for Replicated Secret Sharing without Pre-Processing
* Authors: Martin Zbudila, Erik Pohle, Aysajan Abidin, Bart Preneel
* [Permalink](https://eprint.iacr.org/2024/1026)
* [Download](https://eprint.iacr.org/2024/1026.pdf)

### Abstract

Secure multi-party computation (MPC) in a three-party, honest majority scenario is currently the state-of-the-art for running machine learning algorithms in a privacy-preserving manner. For efficiency reasons, fixed-point arithmetic is widely used to approximate computation over decimal numbers. After multiplication in fixed-point arithmetic, truncation is required to keep the result's precision. In this paper, we present an efficient three-party truncation protocol secure in the presence of an active adversary without pre-processing and improve on the current state-of-the-art in MPC over rings using replicated secret sharing (RSS). By adding an efficient consistency check, we lift the efficient but only passively secure three-party truncation protocol from the ABY3 framework by Mohassel and Rindal into the malicious setting without pre-processed data. Our benchmark indicates performance improvements of an order of magnitude in the offline phase for a single batch training. Finally, we apply our protocol to a real-world application for diagnostic prediction based on publicly available ECG heartbeat data. We achieve an improvement by a factor of two in the total throughput for both LAN and WAN settings.



## 2024/1027

* Title: Structured-Seed Local Pseudorandom Generators and their Applications
* Authors: Dung Bui, Geoffroy Couteau, Nikolas Melissaris
* [Permalink](https://eprint.iacr.org/2024/1027)
* [Download](https://eprint.iacr.org/2024/1027.pdf)

### Abstract

In this note, we introduce structured-seed local pseudorandom generators, a relaxation of local pseudorandom generators. We provide constructions of this primitive under the sparse-LPN assumption, and explore its implications.



## 2024/1028

* Title: FASIL: A challenge-based framework for secure and privacy-preserving federated learning
* Authors: Ferhat Karakoç, Betül Güvenç Paltun, Leyli Karaçay, Ömer Tuna, Ramin Fuladi, Utku Gülen
* [Permalink](https://eprint.iacr.org/2024/1028)
* [Download](https://eprint.iacr.org/2024/1028.pdf)

### Abstract

Enhancing privacy in federal learning (FL) without considering robustness can create an open door for attacks such as poisoning attacks on the FL process. Thus, addressing both the privacy and security aspects simultaneously becomes vital. Although, there are a few solutions addressing both privacy and security in the literature in recent years, they have some drawbacks such as requiring two non-colluding servers, heavy cryptographic operations, or peer-to-peer communication topology. In this paper, we introduce a novel framework that allows the server to run some analysis for detection and mitigation of attacks towards the FL process, while satisfying the confidentiality requirements for the training data against the server. We evaluate the effectiveness of the framework in terms of security and privacy by performing experiments on some concrete examples. We also provide two instantiations  of the framework with two different secure aggregation protocols to give a more concrete view how the framework works and we analyse  the computation and communication overhead of the framework.



## 2024/1029

* Title: Oblivious Single Access Machines: A New Model for Oblivious Computation
* Authors: Ananya Appan, David Heath, Ling Ren
* [Permalink](https://eprint.iacr.org/2024/1029)
* [Download](https://eprint.iacr.org/2024/1029.pdf)

### Abstract

Oblivious RAM (ORAM) allows a client to securely outsource memory storage to an untrusted server. It has been shown that no ORAM can simultaneously achieve small bandwidth blow-up, small client storage, and a single roundtrip of latency.

We consider a weakening of the RAM model, which we call the Single Access Machine (SAM) model. In the SAM model, each memory slot can be written to at most once and read from at most once. We adapt existing tree-based ORAM to obtain an oblivious SAM (OSAM) that has $O(\log n)$ bandwidth blow-up (which we show is optimal), small client storage, and a single roundtrip.

OSAM unlocks improvements to oblivious data structures/algorithms. For instance, we achieve oblivious unbalanced binary trees (e.g. tries, splay trees). By leveraging splay trees, we obtain a notion of caching ORAM, where an access in the worst case incurs amortized $O(\log^2 n)$ bandwidth blow-up and $O(\log n)$ roundtrips, but in many common cases (e.g. sequential scans) incurs only amortized $O(\log n)$ bandwidth blow-up and $O(1)$ roundtrips. We also give new oblivious graph algorithms, including computing minimum spanning trees and single source shortest paths, in which the OSAM client reads/writes $O(|E| \cdot \log |E|)$ words using $O(|E|)$ roundtrips, where $|E|$ is the number of edges. This improves over prior custom solutions by a log factor.

At a higher level, OSAM provides a general model for oblivious computation. We construct a programming interface around OSAM that supports arbitrary pointer-manipulating programs such that dereferencing a pointer to an object incurs $O(\log d \log n)$ bandwidth blowup and $O(\log d)$ roundtrips, where $d$ is the number of pointers to that object. This new interface captures a wide variety of data structures and algorithms (e.g., trees, tries, doubly-linked lists) while matching or exceeding prior best asymptotic results. It both unifies much of our understanding of oblivious computation and allows the programmer to write oblivious algorithms combining various common data structures/algorithms and beyond.



## 2024/1030

* Title: GRASP: Accelerating Hash-based PQC Performance on GPU Parallel Architecture
* Authors: Yijing Ning, Jiankuo Dong, Jingqiang Lin, Fangyu Zheng, Yu Fu, Zhenjiang Dong, Fu Xiao
* [Permalink](https://eprint.iacr.org/2024/1030)
* [Download](https://eprint.iacr.org/2024/1030.pdf)

### Abstract

$SPHINCS^+$, one of the Post-Quantum Cryptography Digital Signature Algorithms (PQC-DSA) selected by NIST in the third round, features very short public and private key lengths but faces significant performance challenges compared to other post-quantum cryptographic schemes, limiting its suitability for real-world applications. To address these challenges, we propose the GPU-based paRallel Accelerated $SPHINCS^+$ (GRASP), which leverages GPU technology to enhance the efficiency of $SPHINCS^+$ signing and verification processes. We propose an adaptable parallelization strategy for $SPHINCS^+$, analyzing its signing and verification processes to identify critical sections for efficient parallel execution. Utilizing CUDA, we perform bottom-up optimizations, focusing on memory access patterns and hypertree computation, to enhance GPU resource utilization. These efforts, combined with kernel fusion technology, result in significant improvements in throughput and overall performance. Extensive experimentation demonstrates that our optimized CUDA implementation of $SPHINCS^+$ achieves superior performance. Specifically, our GRASP scheme delivers throughput improvements ranging from 1.37× to 5.13× compared to state-of-the-art GPU-based solutions and surpasses the NIST reference implementation by over three orders of magnitude, highlighting a significant performance advantage.



## 2024/1031

* Title: SACfe: Secure Access Control in Functional Encryption with Unbounded Data
* Authors: Uddipana Dowerah, Subhranil Dutta, Frank Hartmann, Aikaterini Mitrokotsa, Sayantan Mukherjee, Tapas Pal
* [Permalink](https://eprint.iacr.org/2024/1031)
* [Download](https://eprint.iacr.org/2024/1031.pdf)

### Abstract

Privacy is a major concern in large-scale digital applications, such as cloud-computing, machine learning services, and access control. Users want to protect not only their plain data but also their associated attributes (e.g., age, location, etc). Functional encryption (FE) is a cryptographic tool that allows fine-grained access control over encrypted data. However, existing FE fall short as they are either inefficient and far from reality or they leak sensitive user-specific information.

We propose SACfe, a novel attribute-based FE scheme that provides secure, fine-grained access control and hides both the user’s attributes and the function applied to the data, while preserving the data’s confidentiality. Moreover, it enables users to encrypt unbounded-length messages along with an arbitrary number of hidden attributes into ciphertexts. We design SACfe, a protocol for performing linear computation on encrypted data while enforcing access control based on inner product predicates. We show how SACfe can be used for online biometric authentication for privacy-preserving access control. As an additional contribution, we introduce an attribute-based linear FE for unbounded length of messages and functions where access control is realized by monotone span programs. We implement our protocols using the CiFEr cryptographic library and show its efficiency for practical settings.



## 2024/1032

* Title: Threshold OPRF from Threshold Additive HE
* Authors: Animesh Singh, Sikhar Patranabis, Debdeep Mukhopadhyay
* [Permalink](https://eprint.iacr.org/2024/1032)
* [Download](https://eprint.iacr.org/2024/1032.pdf)

### Abstract

An oblivious pseudorandom function (OPRF) is a two-party protocol in which a party holds an input and the other party holds the PRF key, such that the party having the input only learns the PRF output and the party having the key would not learn the input. Now, in a threshold oblivious pseudorandom function (TOPRF) protocol, a PRF key K is initially shared among T servers. A client can obtain a PRF value by interacting with t(≤ T) servers but is unable to compute the same with up to (t − 1) servers. In this paper, we present a practically efficient homomorphic encryption (HE)-based post-quantum secure TOPRF protocol. Our proposed approach, which is based on a novel use of threshold HE, is agnostic of the underlying PRF and outperforms existing fully homomorphic encryption (FHE)-based approaches for TOPRF computation by several orders of magnitude in terms of running time. The FHE-based approaches require bootstrapping, a computationally extensive operation, and the primary bottleneck for evaluating large-depth circuits. Whereas, our proposed approach is based on a multi-party computation (MPC) protocol that uses a threshold additive HE scheme based on Regev’s cryptosystem (J’ACM 2009) alternative to FHE-based approaches. Concretely, we show a novel replacement of bootstrapping required in traditional FHE schemes by a threshold additive HE-based interactive protocol that performs masked decryption followed by table look-ups, jointly performed by a group of servers holding secret shares of the HE decryption key. Finally, We present a practical validation of our approach by realizing an AES-based TOPRF with an evaluation time of less than 1 second on consumer-grade server(s).



## 2024/1033

* Title: Adaptively Secure 5 Round Threshold Signatures from MLWE/MSIS and DL with Rewinding
* Authors: Shuichi Katsumata, Michael Reichle, Kaoru Takemure
* [Permalink](https://eprint.iacr.org/2024/1033)
* [Download](https://eprint.iacr.org/2024/1033.pdf)

### Abstract

T-out-of-N threshold signatures have recently seen a renewed interest, with various types now available, each offering different tradeoffs.
However, one property that has remained elusive is adaptive security. When we target thresholdizing existing efficient signatures schemes based on the Fiat-Shamir paradigm such as Schnorr, the elusive nature becomes clear. This class of signature schemes typically rely on the forking lemma to prove unforgeability. That is, an adversary is rewound and run twice within the security game. Such a proof is at odds with adaptive security, as the  reduction must be ready to answer 2(T-1) secret key shares in total, implying that it can reconstruct the full secret key. Indeed, prior works either assumed strong idealized models such as the algebraic group model (AGM) or modified the underlying signature scheme so as not to rely on rewinding based proofs.

In this work, we propose a new proof technique to construct adaptively secure threshold signatures for existing rewinding-based Fiat-Shamir signatures. As a result, we obtain the following:
1. The first adaptively secure 5 round lattice-based threshold signature under the MLWE and MSIS assumptions in the ROM. The resulting signature is a standard signature of Raccoon, a lattice-based signature scheme by del Pino et al.., submitted to the additional NIST call for proposals.
2. The first adaptively secure 5 round threshold signature under the DL assumption in the ROM. The resulting signature is a standard Schnorr signature. To the best of our knowledge, this is the first adaptively secure threshold signature based on DL  even assuming stronger models like AGM.

Our work is inspired by the recent statically secure lattice-based 3 round threshold signature by del Pino et al. (Eurocrypt~2024) based on Raccoon. While they relied on so-called one-time additive masks to solve lattice specific issues, we notice that these masks can also be a useful tool to achieve adaptive security. At a very high level, we use these masks throughout the signing protocol to carefully control the information the adversary can learn from the signing transcripts. Intuitively, this allows the reduction to return a total of 2(T-1) randomly sampled secret key shares to the adversary consistently and without being detected, resolving the above paradoxical situation. Lastly, by allowing the parties to maintain a simple state, we can compress our 5 round schemes into 4 rounds.



## 2024/1034

* Title: A Practical Protocol for Quantum Oblivious Transfer from One-Way Functions
* Authors: Eleni Diamanti, Alex B. Grilo, Adriano Innocenzi, Pascal Lefebvre, Verena Yacoub, Álvaro Yángüez
* [Permalink](https://eprint.iacr.org/2024/1034)
* [Download](https://eprint.iacr.org/2024/1034.pdf)

### Abstract

We present a new simulation-secure quantum oblivious transfer (QOT) protocol based on one-way functions in the plain model. With a focus on practical implementation, our protocol surpasses prior works in efficiency, promising feasible experimental realization. We address potential experimental errors and their correction, offering analytical expressions to facilitate the analysis of the required quantum resources. Technically, we achieve simulation security for QOT through an equivocal and relaxed-extractable quantum bit commitment.



## 2024/1035

* Title: Reading It like an Open Book: Single-trace Blind Side-channel Attacks on Garbled Circuit Frameworks
* Authors: Sirui Shen, Chenglu Jin
* [Permalink](https://eprint.iacr.org/2024/1035)
* [Download](https://eprint.iacr.org/2024/1035.pdf)

### Abstract

Garbled circuits (GC) are a secure multiparty computation protocol that enables two parties to jointly compute a function using their private data without revealing it to each other. While garbled circuits are proven secure at the protocol level, implementations can still be vulnerable to side-channel attacks. Recently, side-channel analysis of GC implementations has garnered significant interest from researchers.

We investigate popular open-source GC frameworks and discover that the AES encryption used in the garbling process follows a secret-dependent sequence. This vulnerability allows private inputs to be exposed through side-channel analysis. Based on this finding, we propose a side-channel attack on garbled circuits to recover the private inputs of both parties. Our attack does not require access to any plaintexts or ciphertexts in the protocol and is single-trace, adhering to the constraint that a garbled circuit can be executed only once. Furthermore, unlike existing attacks that can only target input non-XOR gates, our method applies to both input and internal non-XOR gates. Consequently, the secrets associated with every non-XOR gate are fully exposed as in an open book.

We comprehensively evaluate our attack in various scenarios. First, we perform the attack on single-platform software implementations of standard AES and interleaved AES on a 32-bit ARM processor, achieving a $100\%$ success rate in both cases. Next, we target a hardware implementation on a Xilinx Artix-7 FPGA, where the resolution of power consumption measurements and the number of samples are significantly limited. In this scenario, our attack achieves a success rate of $79.58\%$. Finally, we perform a cross-platform attack on two processors with different microarchitectures representing the two parties. The differing execution cycles and power sensors across the platforms increase the difficulty of side-channel analysis. Despite these challenges, our point-of-interest (POI) selection method allows our attack to achieve a $100\%$ success rate in this scenario as well. We also discuss effective countermeasures that can be readily applied to GC frameworks to mitigate this vulnerability.



## 2024/1036

* Title: A note on the G-FFT
* Authors: Ulrich Haboeck
* [Permalink](https://eprint.iacr.org/2024/1036)
* [Download](https://eprint.iacr.org/2024/1036.pdf)

### Abstract

For primes $p$ with $p+1$ being smooth, the G-FFT from Li and Xing [LX23] is an algebraic FFT, which at first glance seems equivalent to the circle FFT from [IACR eprint 2024/278]: It also uses the circle curve over $\mathbb F_p$ (in other words the projective line) as underlying domain, and interpolates by low-degree functions with poles over the same set of points. However, their approach to control the degree of the FFT basis is fundamentally different.
The G-FFT makes use of punctured Riemann-Roch spaces, and the construction works with the group doubling map only, no projection onto the $x$-axis involved. 

In this note we give an elementary description of the G-FFT without using abstract algebra. We describe a variant which uses a simpler, and in our opinion more natural function space, and which treats the exceptional point of the domain (the group identity) differently. In comparison to the circle FFT, the G-FFT (both the original as well as our variant) has the following downsides. Interpolation and domain evaluation costs the double number of multiplications (the twiddle is not an ``odd'' function), and the function space is not invariant under the group action, causing additional overhead when applied in STARKs.



## 2024/1037

* Title: A  note on adding zero-knowledge to STARKs
* Authors: Ulrich Haboeck, Al Kindi
* [Permalink](https://eprint.iacr.org/2024/1037)
* [Download](https://eprint.iacr.org/2024/1037.pdf)

### Abstract

We discuss zero-knowledge in the context of FRI-based STARKs using techniques desirable in practice: Randomization by polynomials over the basefield, and decomposing the overall quotient into polynomials of smaller degree.



## 2024/1038

* Title: Constraint-Packing and the Sum-Check Protocol over Binary Tower Fields
* Authors: Quang Dao, Justin Thaler
* [Permalink](https://eprint.iacr.org/2024/1038)
* [Download](https://eprint.iacr.org/2024/1038.pdf)

### Abstract

SNARKs based on the sum-check protocol often invoke the ``zero-check PIOP''. This reduces the vanishing of many constraints to a single sum-check instance applied to an $n$-variate polynomial of the form $g(x) = \text{eq}(r,x) \cdot p(x)$, where $p$ is a product of multilinear polynomials, $r$ is a random vector, and $\text{eq}$ is the multilinear extension of the equality function. In recent SNARK designs, $p(x)$ is defined over a ``small'' base field, while $r$ is drawn from a large extension field $\mathbb{F}$ for security.

Recent papers (Bagad, Domb, and Thaler 2024; Gruen 2024) have optimized the sum-check protocol prover for this setting. However, these works still require the prover to ``pre-compute'' all evaluations of $\text{eq}(r, x)$ as $x$ ranges over $\{0, 1\}^{n}$,
and this computation involves about $n$ multiplications over the extension field $\mathbb{F}$.
 
In this note, we describe a modification to the zero-check PIOP in the case of binary tower fields that reduces this ``pre-computation'' cost by a factor of close to $\log |\mathbb{F}|$, which is $128$ in important applications. We show that our modification is sound, and that it strictly generalizes a (possibly folklore) technique of constraint-packing over field extensions.



## 2024/1039

* Title: Reduction from Average-Case M-ISIS to Worst-Case CVP Over Perfect Lattices
* Authors: Samuel Lavery
* [Permalink](https://eprint.iacr.org/2024/1039)
* [Download](https://eprint.iacr.org/2024/1039.pdf)

### Abstract

This paper presents a novel reduction from the average-case hardness of the Module Inhomogeneous Short Integer Solution (M-ISIS) problem to the worst-case hardness of the Closest Vector Problem (CVP) by defining and leveraging “perfect” lattices for cryptographic purposes.

Perfect lattices, previously only theoretical constructs, are characterized by their highly regular structure, optimal density, and a central void, which we term the “Origin Cell.” The simplest Origin Cell is a hypercube with edge length 1 centered at the origin, guaranteed to be devoid of any valid lattice points.

By exploiting the unique properties of the Origin Cell, we recalibrate the parameters of the M-ISIS and CVP problems. Our results demonstrate that solving M-ISIS on average over perfect lattices is at least as hard as solving CVP in the worst case, thereby providing a robust hardness guarantee for M-ISIS. Additionally, perfect lattices facilitate exceptionally compact cryptographic variables, enhancing the efficiency of cryptographic schemes.

This significant finding enhances the theoretical foundation of lattice-based cryptographic problems and confirms the potential of perfect lattices in ensuring strong cryptographic security. The Appendix includes SageMath code to demonstrate the reproducibility of the reduction process from M-ISIS to CVP.



## 2024/1040

* Title: PeaceFounder: centralised E2E verifiable evoting via pseudonym braiding and history trees
* Authors: Janis Erdmanis
* [Permalink](https://eprint.iacr.org/2024/1040)
* [Download](https://eprint.iacr.org/2024/1040.pdf)

### Abstract

PeaceFounder is a centralised E2E verifiable e-voting system that leverages pseudonym braiding and history trees. The immutability of the bulletin board is maintained replication-free by voter’s client devices with locally stored consistency-proof chains. Meanwhile, pseudonym braiding done via an exponentiation mix before the vote allows anonymisation to be transactional with a single braider at a time. In contrast to existing E2E verifiable e-voting systems, it is much easier to deploy as the system is fully centralised, free from threshold decryption ceremonies, trusted setup phases and bulletin board replication. Furthermore, the body of a vote is signed with a braided pseudonym, enabling unlimited ballot types.



## 2024/1041

* Title: Embedding Integer Lattices as Ideals into Polynomial Rings
* Authors: Yihang Cheng, Yansong Feng, Yanbin Pan
* [Permalink](https://eprint.iacr.org/2024/1041)
* [Download](https://eprint.iacr.org/2024/1041.pdf)

### Abstract

Many lattice-based crypstosystems employ ideal lattices for high efficiency. However, the additional algebraic structure of ideal lattices usually makes us worry about the security, and it is widely believed that the algebraic structure will help us solve the hard problems in ideal lattices more efficiently.. In this paper, we study the additional algebraic structure of ideal lattices further and find that a given ideal lattice in a polynomial ring can be embedded as  an ideal into infinitely many different polynomial rings by the coefficient embedding. We design an algorithm to verify whether a given full-rank lattice in $\mathbb{Z}^n$ is an ideal lattice and output all the polynomial rings that the given lattice can be embedded into as an ideal with bit operations $\mathcal{O}(n^3(\log n + B)^2(\log n)^2)$, where $n$ is the dimension of the lattice and $B$ is the upper bound of the bit length of the entries of the input lattice basis. We would like to point out that Ding and Lindner proposed an algorithm for identifying ideal lattices and outputting a single polynomial ring of which the input lattice can be regarded as an ideal with bit operations $\mathcal{O}(n^5B^2)$ in 2007. However, we find a flaw in Ding and Lindner's algorithm, and it causes some ideal lattices can't be identified by their algorithm.



## 2024/1042

* Title: Efficient Verifiable Differential Privacy with Input Authenticity in the Local and Shuffle Model
* Authors: Tariq Bontekoe, Hassan Jameel Asghar, Fatih Turkmen
* [Permalink](https://eprint.iacr.org/2024/1042)
* [Download](https://eprint.iacr.org/2024/1042.pdf)

### Abstract

Local differential privacy (LDP) is an efficient solution for providing privacy to client's sensitive data while simultaneously releasing aggregate statistics without relying on a trusted central server (aggregator) as in the central model of differential privacy. The shuffle model with LDP provides an additional layer of privacy, by disconnecting the link between clients and the aggregator, further improving the utility of LDP. However, LDP has been shown to be vulnerable to malicious clients who can perform both input and output manipulation attacks, i.e., before and after applying the LDP mechanism, to skew the aggregator's results. In this work, we show how to prevent malicious clients from compromising LDP schemes. Specifically, we give efficient constructions to prevent both input ánd output manipulation attacks from malicious clients for generic LDP algorithms. Our proposed schemes for verifiable LDP (VLDP), completely protect from output manipulation attacks, and prevent input attacks using signed data, requiring only one-time interaction between client and server, unlike existing alternatives [28, 33]. Most importantly, we are the first to provide an efficient scheme for VLDP in the shuffle model. We describe and prove secure, two schemes for VLDP in the regular model, and one in the shuffle model. We show that all schemes are highly practical, with client runtimes of < 2 seconds, and server runtimes of 5-7 milliseconds per client.



## 2024/1043

* Title: Cryptography in the Common Haar State Model: Feasibility Results and Separations
* Authors: Prabhanjan Ananth, Aditya Gulati, Yao-Ting Lin
* [Permalink](https://eprint.iacr.org/2024/1043)
* [Download](https://eprint.iacr.org/2024/1043.pdf)

### Abstract

Common random string model is a popular model in classical cryptography. We study a quantum analogue of this model called the common Haar state (CHS) model. In this model, every party participating in the cryptographic system receives many copies of one or more i.i.d Haar random states.

We study feasibility and limitations of cryptographic primitives in this model and its variants:

 - We present a construction of pseudorandom function-like states with security against computationally unbounded adversaries, as long as the adversaries only receive (a priori) bounded number of copies. By suitably instantiating the CHS model, we obtain a new approach to construct pseudorandom function-like states in the plain model.

 - We present separations between pseudorandom function-like states (with super-logarithmic length) and quantum cryptographic primitives, such as interactive key agreement and bit commitment, with classical communication. To show these separations, we prove new results on the indistinguishability of identical versus independent Haar states against LOCC (local operations, classical communication) adversaries.



## 2024/1044

* Title: Searching for differential addition chains
* Authors: Daniel J. Bernstein, Jolijn Cottaar, Tanja Lange
* [Permalink](https://eprint.iacr.org/2024/1044)
* [Download](https://eprint.iacr.org/2024/1044.pdf)

### Abstract

The literature sometimes uses slow algorithms to find minimum-length continued-fraction differential addition chains to speed up subsequent computations of multiples of points on elliptic curves. This paper introduces two faster algorithms to find these chains. The first algorithm prunes more effectively than previous algorithms. The second algorithm uses a meet-in-the-middle approach and appears to have a limiting cost exponent below 1.



## 2024/1045

* Title: Efficient Secret Sharing for Large-Scale Applications
* Authors: Sarvar Patel, Giuseppe Persiano, Joon Young Seo, Kevin Yeo
* [Permalink](https://eprint.iacr.org/2024/1045)
* [Download](https://eprint.iacr.org/2024/1045.pdf)

### Abstract

Threshold secret sharing enables distributing a message to $n$ parties such that no subset of fewer than $t$ parties can learn the message, whereas any subset of at least $t$ parties can recover the message. Despite being a fundamental primitive, secret sharing still suffers from one significant drawback, where its message reconstruction algorithm is computationally expensive for large privacy thresholds $t$. In this paper, we aim to address this significant drawback.

We study general $(t,c)$-ramp secret sharing schemes where the number of parties c needed to reconstruct the secret may be larger than $t$. We present a ramp secret sharing scheme whose reconstruction time is 2-7.8x faster than prior constructions suitable against adversaries that adaptively corrupt parties.. For $t = 2^{20}$, our new protocol has reconstruction time of 5 seconds whereas prior work requires nearly half a minute. We see improvements starting from as small as $t = 256$. Furthermore, we obtain correctness threshold as small as $c \ge 1.05t$. To obtain our construction, we first improve the secret sharing frameworks by Cramer et al. (EUROCRYPT'15) and Applebaum et al. (CRYPTO'23) from erasure codes. Our new framework obtains secret sharing schemes that may be used against adversaries with adaptive corruptions while requiring only weaker correctness guarantees from the underlying erasure code with a distributed generation property. Furthermore, our new framework also maintains the linear homomorphism of the prior works. Afterwards, we present a concretely efficient erasure code from random band matrices that satisfies the distributed generation property.

We show that our secret sharing scheme can improve many real-world applications. In secure aggregation protocols for federated learning, we obtain up to 22% reductions in computational cost by replacing Shamir's scheme with our construction. We extend our protocol to obtain a verifiable ramp secret sharing scheme where each party can verify the consistency of the shares. Our new verifiable ramp secret sharing has 8.2-25.2x faster sharing and 2.7-23.2x faster reconstruction time compared to prior works. Finally, we present an improved distributed verifiable random function that may be used for decentralized randomness beacons.



## 2024/1046

* Title: The Sum-Check Protocol over Fields of Small Characteristic
* Authors: Suyash Bagad, Yuval Domb, Justin Thaler
* [Permalink](https://eprint.iacr.org/2024/1046)
* [Download](https://eprint.iacr.org/2024/1046.pdf)

### Abstract

The sum-check protocol of Lund, Fortnow, Karloff, and Nisan underlies SNARKs with the fastest known prover. In many of its applications, the prover can be implemented with a number of field operations that is linear in the number, $n$, of terms being summed.

We describe an optimized prover implementation when the protocol is applied over an extension field of a much smaller base field. The rough idea is to keep most of the prover's multiplications over the base field, at the cost of performing more $\textit{total}$ field multiplications. When the sum-check protocol is applied to a product of polynomials that all output values in the base field, our algorithm reduces the number of extension field operations by multiple orders of magnitude. In other settings, our improvements are more modest but nonetheless meaningful.

In SNARK design, the sum-check protocol is often combined with a polynomial commitment scheme, which are growing faster, especially when the values being committed are small. These improved commitment schemes are likely to render the sum-check prover the overall bottleneck, which our results help to mitigate.



## 2024/1047

* Title: Improved Multi-Party Fixed-Point Multiplication
* Authors: Saikrishna Badrinarayanan, Eysa Lee, Peihan Miao, Peter Rindal
* [Permalink](https://eprint.iacr.org/2024/1047)
* [Download](https://eprint.iacr.org/2024/1047.pdf)

### Abstract

Machine learning is widely used for a range of applications and is increasingly offered as a service by major technology companies. However, the required massive data collection raises privacy concerns during both training and inference. Privacy-preserving machine learning aims to solve this problem. In this setting, a collection of servers secret share their data and use secure multi-party computation to train and evaluate models on the joint data. All prior work focused on the scenario where the number of servers is two or three. In this work, we study the problem where there are $N \geq 3$ servers amongst whom the data is secret shared.

A key component of machine learning algorithms is to perform fixed-point multiplication with truncation of secret shared decimal values. In this work, we design new protocols for multi-party secure fixed-point multiplication where each of the $N$ parties have one share each of the two values to be multiplied and receive one share of the product at the end of the protocol. We consider three forms of secret sharing - replicated, Shamir, and additive, and design an efficient protocol secure in the presence of a semi-honest adversary for each of the forms. Our protocols are more communication efficient than all prior work on performing multi-party fixed-point multiplication. Additionally, for replicated secret sharing, we design another efficient protocol that is secure in the presence of a malicious adversary. Finally, we leverage our fixed-point multiplication protocols to design secure multi-party computation (MPC) protocols for arbitrary arithmetic circuits that have addition and fixed-point multiplication with truncation gates. All our protocols are proven secure using a standard simulation based security definition. Our protocols for replicated and Shamir sharing work in the presence of an honest majority of parties while the one for additive sharing can tolerate a dishonest majority as well.



## 2024/1048

* Title: Distributional Secure Merge
* Authors: Gayathri Garimella, Srinivasan Raghuramam, Peter Rindal
* [Permalink](https://eprint.iacr.org/2024/1048)
* [Download](https://eprint.iacr.org/2024/1048.pdf)

### Abstract

Secure merge refers to the problem of merging two sorted lists. The problem appears in different settings where each list is held by one of two parties, or the lists are themselves shared among two or more parties. The output of a secure merge protocol is secret shared. Each variant of the problem offers many useful applications.

The difficulty in designing secure merge protocols vis-a-vis insecure merge protocols (which work in linear time with a single pass over the lists) has to do with operations having to be oblivious or data-independent. In particular, the protocol cannot leak the positions of items of each list in the final merged list. On account of this, sorting-based secure merge protocols have been a common solution to the problem. However, as they introduce (poly)logarithmic overheads, there has been active investigation into the task of building (near) linear time secure merge protocols. Most recently, Hemenway et al. put forth a protocol for secure merge that does achieve linear communication and computation and a round complexity of $O({\log\log n})$, where $n$ is the length of the lists being merged. While this shows the feasibility of a linear time secure merge, it still leaves room for the design of a concretely efficient linear time secure merge.

In this work, we consider a relaxation of the problem where the lists are uniformly random. We show a secure merge protocol for uniformly random lists that achieves $O({n\log\log n})$, i.e., near linear communication and computation and a round complexity of $O({\log\log n})$, where $n$ is the length of the lists being merged. Our protocol design is general and can be instantiated in a variety of settings so long as the building blocks (basic ones such as comparisons and shuffles) can be realized in said settings. Although we do not achieve the same asymptotic guarantees as Hemenway et al., our work is concretely efficient. We implement our protocol and compare it to the state of the art sorting protocols and demonstrate an order of magnitude improvement in running times and communication for lists of size of $2^{20}$.

We also extend our protocol to work for lists sampled from arbitrary distributions. In particular, when the lists are (close to) identically distributed, we achieve the same efficiency as uniform lists. This immediately improve the performance of many crucial applications including PSI & Secure Join, thus illustrating the significance and applicability of our protocol in practice.



## 2024/1049

* Title: KyberSlash: Exploiting secret-dependent division timings in Kyber implementations
* Authors: Daniel J. Bernstein, Karthikeyan Bhargavan, Shivam Bhasin, Anupam Chattopadhyay, Tee Kiah Chia, Matthias J. Kannwischer, Franziskus Kiefer, Thales Paiva, Prasanna Ravi, Goutam Tamvada
* [Permalink](https://eprint.iacr.org/2024/1049)
* [Download](https://eprint.iacr.org/2024/1049.pdf)

### Abstract

This paper presents KyberSlash1 and KyberSlash2 – two timing vulnerabilities in several implementations (including the official reference code) of the Kyber Post-Quantum Key Encapsulation Mechanism, currently undergoing standardization as ML-KEM. We demonstrate the exploitability of both KyberSlash1 and KyberSlash2 on two popular platforms: the Raspberry Pi 2 (Arm Cortex-A7) and the Arm Cortex-M4 microprocessor. Kyber secret keys are reliably recovered within minutes for KyberSlash2 and a few hours for KyberSlash1.
We responsibly disclosed these vulnerabilities to maintainers of various libraries and they have swiftly been patched. We present two approaches for detecting and avoiding similar vulnerabilities. First, we patch the dynamic analysis tool Valgrind to allow detection of variable-time instructions operating on secret data, and apply it to more than 1000 implementations of cryptographic primitives in SUPERCOP. We report multiple findings. Second, we propose a more rigid approach to guarantee the absence of variable-time instructions in cryptographic software using formal methods.



## 2024/1050

* Title: On Sequential Functions and Fine-Grained Cryptography
* Authors: Jiaxin Guan, Hart Montgomery
* [Permalink](https://eprint.iacr.org/2024/1050)
* [Download](https://eprint.iacr.org/2024/1050.pdf)

### Abstract

A sequential function is, informally speaking, a function $f$ for which a massively parallel adversary cannot compute "substantially" faster than an honest user with limited parallel computation power. Sequential functions form the backbone of many primitives that are extensively used in blockchains such as verifiable delay functions (VDFs) and time-lock puzzles. Despite this widespread practical use, there has been little work studying the complexity or theory of sequential functions.

Our main result is a black-box oracle separation between sequential functions and one-way functions: in particular, we show the existence of an oracle $\mathcal{O}$ that implies a sequential function but not a one-way function. This seems surprising since sequential functions are typically constructed from very strong assumptions that imply one-way functions and also since time-lock puzzles are known to imply one-way functions (Bitansky et al., ITCS '16).

We continue our exploration of the theory of sequential functions. We show that, informally speaking, the decisional, worst-case variant of a certain class of sequential function called a continuous iterative sequential function (CISF) is PSPACE-complete. A CISF is, in a nutshell, a sequential function $f$ that can be written in the form $f \left(k, x \right) = g^{k} \left(x \right)$ for some function $g$ where $k$ is an input determining the number of "rounds" the function is evaluated. We then show that more general forms of sequential functions are not contained in PSPACE relative to a random oracle.

Given these results, we then ask if it is possible to build any interesting cryptographic primitives from sequential functions that are not one-way. It turns out that even if we assume just the existence of a CISF that is not one-way, we can build certain "fine-grained" cryptographic primitives where security is defined similarly to traditional primitives with the exception that it is only guaranteed for some (generally polynomial) amount of time. In particular, we show how to build "fine-grained" symmetric key encryption and "fine-grained" MACs from a CISF. We also show how to build fine-grained public-key encryption from a VDF with a few extra natural properties and indistinguishability obfucsation (iO) for null circuits. We do not assume one-way functions. Finally, we define a primitive that we call a commutative sequential function - essentially a sequential function that can be computed in sequence to get the same output in two different ways - and show that it implies fine-grained key exchange.



## 2024/1051

* Title: Adaptor Signatures: New Security Definition and A Generic Construction for NP Relations
* Authors: Xiangyu Liu, Tzannetos Ioannis, Vassilis Zikas
* [Permalink](https://eprint.iacr.org/2024/1051)
* [Download](https://eprint.iacr.org/2024/1051.pdf)

### Abstract

An adaptor signatures (AS) scheme is an extension of digital signatures that allows the signer to generate a pre-signature for an instance of a hard relation. This pre-signature can later be adapted to a full signature with a corresponding witness. Meanwhile, the signer can extract a witness from both the pre-signature and the signature. AS have recently garnered more attention due to its scalability and interoperability. Dai et al. [INDOCRYPT 2022] proved that AS can be constructed for any NP relation using a generic construction. However, their construction has a shortcoming: the associated witness is exposed by the adapted signature. This flaw poses limits the applications of AS, even in its motivating setting, i.e., blockchain, where the adapted signature is typically uploaded to the blockchain and is public to everyone.

To address this issue, in this work we augment the security definition of AS by a natural property which we call witness hiding. We then prove the existence of AS for any NP relation, assuming the existence of one-way functions. Concretely, we propose a generic construction of witness-hiding AS from signatures and a weak variant of trapdoor commitments, which we term trapdoor commitments with a specific adaptable message. We instantiate the latter based on the Hamiltonian cycle problem. Since the Hamiltonian cycle problem is NP-complete, we can obtain witness hiding adaptor signatures for any NP relation.



## 2024/1052

* Title: A New Fine Tuning Method for FHEW/TFHE Bootstrapping with IND-CPAD Security
* Authors: Deokhwa Hong, Young-Sik Kim, Yongwoo Lee, Eunyoung Seo
* [Permalink](https://eprint.iacr.org/2024/1052)
* [Download](https://eprint.iacr.org/2024/1052.pdf)

### Abstract

Fully homomorphic encryption (FHE) schemes enable computations on encrypted data, making them a crucial component of privacy-enhancing technologies.
Ducas and Micciancio introduced FHEW (Eurocrypt '15), and Chillotti et al. improved it in TFHE (Asiacrypt '16), both of which provide homomorphic binary (or larger) gate evaluations with fast latency due to their small parameters.
However, their evaluation failure probability is highly sensitive to parameter selection, resulting in a limited set of viable parameters and a trade-off between failure probability and runtime.

Recently, Cheon et al. proposed a key recovery attack against FHEW/TFHE schemes based on a new security model for FHE, called IND-CPA-D security, which was first introduced by Li and Micciancio (Eurocrypt '21).
To prevent this attack, it is necessary to make the failure probability negligible (e.g., $2^{-128}$).
However, due to limited choice parameters, it is forced to use a parameter set with unnecessarily low failure probabilities than needed, causing inefficiencies in runtime.

We propose a new bootstrapping method for FHEW/TFHE, providing a precise balance between runtime and failure probability, and easy to implement.
The proposed methods enable the selection of parameter sets that achieve negligible failure probabilities for each desired security level while optimizing runtime.



## 2024/1053

* Title: Stochastic Secret Sharing with $1$-Bit Shares and Applications to MPC
* Authors: Benny Applebaum, Eliran Kachlon
* [Permalink](https://eprint.iacr.org/2024/1053)
* [Download](https://eprint.iacr.org/2024/1053.pdf)

### Abstract

The problem of minimizing the share size of threshold secret-sharing schemes is a basic research question that has been extensively studied. Ideally, one strives for schemes in which the share size equals the secret size. While this is achievable for large secrets (Shamir, CACM '79), no similar solutions are known for the case of binary, single-bit secrets. Current approaches often rely on so-called ramp secret sharing that achieves a constant share size at the expense of a slight gap between the privacy and the correctness thresholds. In the case of single-bit shares, this leads to a large gap which is typically unacceptable. The possibility of a meaningful notion of secret sharing scheme with 1-bit shares and almost optimal threshold has been left wide open. Of special interest is the case of threshold 0.5, which is motivated by information-theoretic honest-majority secure multiparty computation (MPC).

In this work, we present a new stochastic model for secret-sharing where each party is corrupted by the adversary with probability $p$, independently of the other parties, and correctness and privacy are required to hold with high probability over the choice of the corrupt parties. We present new secret sharing schemes with single-bit shares that tolerate any constant corruption probability $p<0.5$. Our construction is based on a novel connection between such stochastic secret-sharing schemes and error-correcting codes that achieve capacity over the binary erasure channel.

Our schemes are linear and multiplicative. We demonstrate the usefulness of the model by using our new schemes to construct MPC protocols with security against an adversary that passively corrupts an arbitrary subset of $0.499n$ of the parties, where the online communication per party consists of a single bit per AND gate and zero communication per XOR gate. Unlike competing approaches for communication-efficient MPC, our solution is applicable even in a real-time model in which the parties should compute a Boolean circuit whose gates arrive in real-time, one at a time, and are not known in advance.



## 2024/1054

* Title: Optimized Computation of the Jacobi Symbol
* Authors: Jonas Lindstrøm, Kostas Kryptos Chalkias
* [Permalink](https://eprint.iacr.org/2024/1054)
* [Download](https://eprint.iacr.org/2024/1054.pdf)

### Abstract

The Jacobi Symbol is an essential primitive in cryptographic applications such as primality testing, integer factorization, and various encryption schemes.. By exploring the interdependencies among modular reductions within the algorithmic loop, we have developed a refined method that significantly enhances computational efficiency. Our optimized algorithm, implemented in the Rust language, achieves a performance increase of 72% over conventional textbook methods and is twice as fast as the previously fastest known Rust implementation..

This work not only provides a detailed analysis of the optimizations but also includes comprehensive benchmark comparisons to illustrate the practical advantages of our methods. Our algorithm is publicly available under an open-source license, promoting further research on foundational cryptographic optimizations.



## 2024/1055

* Title: Enhancing Local Verification: Aggregate and Multi-Signature Schemes
* Authors: Ahmet Ramazan Ağırtaş, Neslihan Yaman Gökce, Oğuz Yayla
* [Permalink](https://eprint.iacr.org/2024/1055)
* [Download](https://eprint.iacr.org/2024/1055.pdf)

### Abstract

An aggregate signature scheme is a digital signature protocol that enables the aggregation of multiple signatures. Given n signatures on n distinct messages from n different users, it is possible to combine all these signatures into a single, concise signature. This single signature, along with the n original messages, convinces the verifier that the n users indeed signed their respective n original messages. However, the verifier must have access to all the original messages to perform the verification, highlighting a potential limitation in terms of accessibility and efficiency. Goyal and Vaikuntanathan introduced the concept of local verification,
which allows the verifier to determine if a specific message m is part of the aggregated signature by only accessing the message m. In this paper, we extend the single-signer locally verifiable aggregate signature scheme initially proposed by Goyal and Vaikuntanathan, adapting it to a multi-signer context. Our generalization allows the verifier to validate multiple signatures simultaneously using an auxiliary value generated by the LocalOpen algorithm, thereby enhancing verification efficiency. Furthermore, we integrate this approach into the multi-signature scheme proposed by Boneh, Drijvers, and Neven, demonstrating its broader applicability and potential benefits in complex cryptographic systems.



## 2024/1056

* Title: Shuffle Arguments Based on Subset-Checking
* Authors: Behzad Abdolmaleki, Prastudy Fauzi, Toomas Krips, Janno Siim
* [Permalink](https://eprint.iacr.org/2024/1056)
* [Download](https://eprint.iacr.org/2024/1056.pdf)

### Abstract

Zero-knowledge shuffle arguments are a useful tool for constructing mix-nets which enable anonymous communication. We propose a new shuffle argument using a novel technique that probabilistically checks that each weighted set of input elements corresponds to some weighted set of output elements, with weights from the same set as the input element weights. We achieve this using standard discrete log assumptions and the shortest integer solution (SIS) assumption. Our shuffle argument has prover and verifier complexity linear in the size of the shuffled set, and communication complexity logarithmic both in the shuffled set size and security parameter.



## 2024/1057

* Title: Password-authenticated Key Exchange and Applications
* Authors: Kristian Gjøsteen
* [Permalink](https://eprint.iacr.org/2024/1057)
* [Download](https://eprint.iacr.org/2024/1057.pdf)

### Abstract

We analyse a two password-authenticated key exchange protocols, a variant of CPace and a protocol related to the well-known SRP protocol.  Our security results are tight.  The first result gives us some information about trade-offs for design choices in CPace.  The second result provides information about the security of SRP.

Our analysis is done in a new game-based security definition for password-authenticated key exchange.  Our definition accomodates arbitrary password sampling methodologies.  Our definition also supports modular security analysis, which we illustrate by giving two example applications of password-authenticated key exchange: password-authenticated secure channels and password-authenticated device authorisation, capturing popular applications of passwords.



## 2024/1058

* Title: Natively Compatible Super-Efficient Lookup Arguments and How to Apply Them
* Authors: Matteo Campanelli, Dario Fiore, Rosario Gennaro
* [Permalink](https://eprint.iacr.org/2024/1058)
* [Download](https://eprint.iacr.org/2024/1058.pdf)

### Abstract

Lookup arguments allow an untrusted prover to commit to a vector $\vec f \in \mathbb{F}^n$ and show that its entries reside in a predetermined table $\vec t \in \mathbb{F}^N$. One of their key applications is to augment general-purpose SNARKs making them more efficient on subcomputations that are hard to arithmetize. In order for this "augmentation" to work out, a SNARK and a lookup argument should have some basic level of compatibility with respect to the commitment on $\vec f$. However, not all existing efficient lookup arguments are fully compatible with other efficient general-purpose SNARKs. This incompatibility can for example occur whenever SNARKs use multilinear extensions under the hood (e.g. Spartan) but the lookup argument is univariate in flavor (e..g. Caulk or $\mathsf{cq}$).

In this paper we discuss how to widen the spectrum of "super-efficient" lookup arguments (where the proving time is independent of the size of the lookup table): we present a new construction inspired by $\mathsf{cq}$and based on multilinear polynomial encodings (MLE). Our construction is the first lookup argument for any table that is also natively compatible with MLE-based SNARKs at comparable costs with other state-of-the-art lookup arguments, particularly when the large table is unstructured. This case arises in  various applications, such as using lookups to prove that the program in a virtual machine is fetching the right instruction and when proving the correct computation of floating point arithmetic (e.g., in verifiable machine learning).

We also introduce a second more general construction: a compiler that, given any super-efficient lookup argument compatible with univariate SNARKs, converts it into a lookup argument compatible with MLE-based SNARKs with a very small overhead.
Finally, we discuss SNARKs that we can compose with our constructions as well as approaches for this composition to work effectively.



## 2024/1059

* Title: HEProfiler: An In-Depth Profiler of Approximate Homomorphic Encryption Libraries
* Authors: Jonathan Takeshita, Nirajan Koirala, Colin McKechney, Taeho Jung
* [Permalink](https://eprint.iacr.org/2024/1059)
* [Download](https://eprint.iacr.org/2024/1059.pdf)

### Abstract

Fully Homomorphic Encryption (FHE) allows computation on encrypted
data. Various software libraries have implemented the approximate-
arithmetic FHE scheme CKKS, which is highly useful for applications
in machine learning and data analytics; each of these libraries have differing performance and features. It is useful for developers and researchers to learn details about these libraries’ performance and their differences. Some previous work has profiled FHE and CKKS implementations for this purpose, but these comparisons are limited in their fairness and completeness.

In this article, we compare four major libraries supporting the CKKS
scheme. Working with the maintainers of each of the PALISADE,
Microsoft SEAL, HElib, and HEAAN libraries, we devise methods for fair
comparisons of these libraries, even with their widely varied development
strategies and library architectures. To show the practical performance of
these libraries, we present HEProfiler, a simple and extensible framework
for profiling C++ FHE libraries. Our experimental evaluation is complete in both the scope of tasks tested and metrics evaluated, allowing
us to draw conclusions about the behaviors of different libraries under a
wide range of real-world workloads. This is the first work-giving experimental comparisons of different bootstrapping-capable CKKS libraries.



## 2024/1060

* Title: Quirky Interactive Reductions of Knowledge
* Authors: Joseph Johnston
* [Permalink](https://eprint.iacr.org/2024/1060)
* [Download](https://eprint.iacr.org/2024/1060.pdf)

### Abstract

Interactive proofs and arguments of knowledge can be generalized to the concept of interactive reductions of knowledge, where proving knowledge of a witness for one NP language is reduced to proving knowledge of a witness for another NP language. We take this generalization and specialize it to a class of reductions we refer to as `quirky interactive reductions of knowledge' (or QUIRKs). This name reflects our particular design choices within the broad and diverse world of interactive reduction methods. A central design choice is allowing the prover to rewind or regress to any previous reduction and repeat it as many times as desired. We prove completeness and extractability properties for QUIRKs. We also offer tools for constructing extraction algorithms along with several simple examples of usage.



## 2024/1061

* Title: Insta-Pok3r: Real-time Poker on Blockchain
* Authors: Sanjam Garg, Aniket Kate, Pratyay Mukherjee, Rohit Sinha, Sriram Sridhar
* [Permalink](https://eprint.iacr.org/2024/1061)
* [Download](https://eprint.iacr.org/2024/1061.pdf)

### Abstract

We develop a distributed service for generating correlated randomness (e.g. permutations) for multiple parties, where each party’s output is private but publicly verifiable. This service provides users with a low-cost way to play online poker in real-time, without a trusted party.
Our service is backed by a committee of compute providers, who run a multi-party computation (MPC) protocol to produce an (identity-based) encrypted permutation of a deck of cards, in an offline phase well ahead of when the players’ identities are known. When the players join, what we call the online phase, they decrypt their designated cards immediately after deriving the identity-based decryption keys, a much simpler computation. In addition, the MPC protocol also generates a publicly-verifiable proof that the output is a permutation.
In our construction, we introduce a new notion of succinctly verifiable multi-identity based encryption (SVME), which extends the existing notion of verifiable encryption to a multi-identity-based setting, but with a constant sized proof – this may be of independent interest. We instantiate this for a permutation relation (defined over a small set) along with identity-based encryption, polynomial commitments and succinct proofs – our choices are made to enable a distributed computation when the card deck is always secret shared. Moreover, we design a new protocol to efficiently generate a secret-sharing of random permutation of a small set, which is run prior to distributed SVME.
Running these protocols offline simplifies the online phase substantially, as parties only derive their identity-specific keys privately via secure channels with the MPC committee, and then decrypt locally to obtain their decks. We provide a rigorous UC-based formalization in a highly modularized fashion.
Finally, we demonstrate practicality with an implementation that shows that for 8 MPC parties, gen- erating a secret publicly-verifiable permutation of 64 cards takes under 3 seconds, while accessing cards for a player takes under 0.3 seconds.



## 2024/1062

* Title: Compact Key Function Secret Sharing with Non-linear Decoder
* Authors: Chandan Kumar, Sikhar Patranabis, Debdeep Mukhopadhyay
* [Permalink](https://eprint.iacr.org/2024/1062)
* [Download](https://eprint.iacr.org/2024/1062.pdf)

### Abstract

We present a variant of Function Secret Sharing (FSS) schemes tailored for point, comparison, and interval functions, featuring compact key sizes at the expense of additional comparison. While existing FSS constructions are primarily geared towards $2$-party scenarios, exceptions such as the work by Boyle et al. (Eurocrypt 2015) and Riposte (S&P 2015) have introduced FSS schemes for $p$-party scenarios ($p \geq 3$). This paper aims to achieve the most compact $p$-party FSS key size to date. We achieve a noteworthy reduction in key size, a $2^p$-factor decrease compared to state-of-the-art FSS constructions (including computationally efficient constructions using symmetric-key primitives) of distributed point function (DPF). Compared to the previous public-key-based FSS design for DPF, we also get a key size reduction equal to a $2^{n/2}$-sized row vector, where $2^n$ is the domain size of the point function. This reduction in key size comes at the cost of a required comparison operation by the decoder (hence called a non-linear decoder), a departure from prior schemes. In $p$-party scenarios, our construction outperforms existing FSS constructions in key size, remaining on par with Riposte in evaluation time and showing significant improvement over Boyle et al.

In addition to constructing FSS for distributed point functions (DPF), we extend our approach to distributed comparison and interval functions, achieving the most efficient key size to date. Our distributed comparison function exhibits a key-size reduction by a factor of $q^{p-1}$, where $q$ denotes the size of the algebraic group used in the scheme's construction.
The reduced key size of the comparison function has practical implications, particularly in applications like privacy-preserving machine learning (PPML), where thousands of comparison functions are employed in each neural network layer.
To demonstrate the effectiveness of our improvements, we design and prototype-implement a scalable privacy-preserving framework for neural networks over distributed models. Specifically, we implement a distributed rectified linear unit (ReLU) activation function using our distributed comparison function, showcasing the efficacy of our proposed scheme.



## 2024/1063

* Title: VIMz: Verifiable Image Manipulation using Folding-based zkSNARKs
* Authors: Stefan Dziembowski, Shahriar Ebrahimi, Parisa Hassanizadeh
* [Permalink](https://eprint.iacr.org/2024/1063)
* [Download](https://eprint.iacr.org/2024/1063.pdf)

### Abstract

With the rise of generative AI technology, the media's credibility as a source of truth has been significantly compromised. This highlights the need to verify the authenticity of media and its originality.
Ensuring the integrity of media during capture using the device itself presents a straightforward solution to this challenge.
However, raw captured media often require certain refinements or redactions before publication. Zero-knowledge proofs (ZKP) offer a solution by allowing attestation of the correctness of specific transformations applied to an authorized image. While shown to be feasible, previous approaches faced challenges in practice due to their high prover complexity.

In this paper, we aim to develop a practical framework for efficiently proving the authenticity of HD and 4K images on commodity hardware. Our goal is to minimize prover complexity by utilizing the folding-based zkSNARKs technique, resulting in VIMz, the first practical verifiable image manipulation system of this kind. VIMz leverages Nova's folding scheme to achieve low complexity recursive zkSNARK proofs of authentic image manipulation. Our implementation results demonstrate a substantial reduction in prover complexity—up to a 3$\times$ speedup in time and a 96$\times$ reduction in memory (from 309 GB in [Kang et al., arXiv 2022] to only 3.2 GB). Moreover, the low memory consumption allows VIMz to prove the correctness of multiple chained transformations simultaneously, further increasing the performance (up to 3.5$\times$).
Additionally,
we propose a trustless smart contract system that autonomously verifies the proofs of media authenticity, achieving trustless copyright and ownership management, aligning with the standards of the Coalition for Content Provenance and Authenticity (C2PA).
Such a system serves as a foundational infrastructure for constructing trustless media marketplaces with diverse applications.



## 2024/1064

* Title: ArcEDB: An Arbitrary-Precision Encrypted Database via (Amortized) Modular Homomorphic Encryption
* Authors: Zhou Zhang, Song Bian, Zian Zhao, Ran Mao, Haoyi Zhou, Jiafeng Hua, Yier Jin, Zhenyu Guan
* [Permalink](https://eprint.iacr.org/2024/1064)
* [Download](https://eprint.iacr.org/2024/1064.pdf)

### Abstract

Fully homomorphic encryption (FHE) based database outsourcing is drawing growing research interests. At its current state, there exist two primary obstacles against FHE-based encrypted databases (EDBs): i) low data precision, and ii) high computational latency. To tackle the precision-performance dilemma, we introduce ArcEDB, a novel FHE-based SQL evaluation infrastructure that simultaneously achieves high data precision and fast query evaluation. Based on a set of new plaintext encoding schemes, we are able to execute arbitrary-precision ciphertext-to-ciphertext homomorphic comparison orders of magnitude faster than existing methods. Meanwhile, we propose efficient conversion algorithms between the encoding schemes to support highly composite SQL statements, including advanced filter-aggregation and multi-column synchronized sorting. We perform comprehensive experiments to study the performance characteristics of ArcEDB. In particular, we show that ArcEDB can be up to $57\times$ faster in homomorphic filtering and up to $20\times$ faster over end-to-end SQL queries when compared to the state-of-the-art FHE-based EDB solutions. Using ArcEDB, a SQL query over a 10K-row time-series EDB with 64-bit timestamps only runs for under one minute.



## 2024/1065

* Title: AITIA: Efficient Secure Computation of Bivariate Causal Discovery
* Authors: Truong Son Nguyen, Lun Wang, Evgenios M. Kornaropoulos, Ni Trieu
* [Permalink](https://eprint.iacr.org/2024/1065)
* [Download](https://eprint.iacr.org/2024/1065.pdf)

### Abstract

Researchers across various fields seek to understand causal relationships but often find controlled experiments impractical. To address this, statistical tools for causal discovery from naturally observed data have become crucial. Non-linear regression models, such as Gaussian process regression, are commonly used in causal inference but have limitations due to high costs when adapted for secure computation. Support vector regression (SVR) offers an alternative but remains costly in an Multi-party computation context due to conditional branches and support vector updates.

In this paper, we propose Aitia, the first two-party secure computation protocol for bivariate causal discovery. The protocol is based on optimized multi-party computation design choices and is secure in the semi-honest setting. At the core of our approach is BSGD-SVR, a new non-linear regression algorithm designed for MPC applications, achieving both high accuracy and low computation and communication costs. Specifically, we reduce the training complexity of the non-linear regression model from approximately from $\mathcal{O}(N^3)$ to $\mathcal{O}(N^2)$ where $N$ is the number of training samples.
We implement Aitia using CrypTen and assess its performance across various datasets. Empirical evaluations show a significant speedup of $3.6\times$ to $340\times$ compared to the baseline approach.