[continued from previous message]

Lipmaa, Parisella, and Siim [Eurocrypt, 2024] proved the extractability of the KZG polynomial commitment scheme under the falsifiable assumption ARSDH. They also showed that variants of real-world zk-SNARKs like Plonk can be made knowledge-sound in the
random oracle model (ROM) under the ARSDH assumption. However, their approach did not consider various batching optimizations, resulting in their variant of Plonk having approximately 3.5 times longer argument. Our contributions are: (1) We prove that
several batch-opening protocols for KZG, used in modern zk-SNARKs, have computational special-soundness under the ARSDH assumption. (2) We prove that interactive Plonk has computational special-soundness under the ARSDH assumption and a new falsifiable
assumption TriRSDH. We also prove that a minor modification of the interactive Plonk has computational special-soundness under only the ARSDH assumption. The Fiat-Shamir transform can be applied to obtain non-interactive versions, which are secure in the
ROM under the same assumptions.



## 2024/995

* Title: Cross-chain bridges via backwards-compatible SNARKs
* Authors: Sergio Juárez, Mark Blunden, Joris Koopman, Anish Mohammed, Kapil Shenvi Pause, Steve Thakur
* [Permalink](https://eprint.iacr.org/2024/995)
* [Download](https://eprint.iacr.org/2024/995.pdf)

### Abstract

In recent years, SNARKs have shown great promise as a tool for building trustless bridges to connect the heterogeneous ecosystem of blockchains. Unfortunately, the parameters hardwired for many of the widely used blockchains are incongruous with the
conventional SNARKs, which results in unsatisfactory performance. This bottleneck necessitates new proof systems tailored for efficiency in these environments.

The primary focus of this paper is on succinct bridges from Cosmos to Ethereum, which largely boils down to efficient proofs of multiple Ed25519 signatures. However, these techniques can be ported to settings that require succinct proofs of multiple
secp256k1 or BLS12-381 signatures.

We describe our succinct validity bridging scheme Overfly, which uses a field-agnostic SNARK to circumvent the huge overhead of non-native field arithmetic arising from Ed25519 scalar multiplications in the circuit. We also explore the schemes deVirgo
and zkTree, which exploit the parallelization of proof generation and the subsequent aggregation of proofs.

Our benchmarks indicate that it is crucial to sidestep non-native arithmetic to the extent that it is possible. We also found that two or more proof systems need to be securely amalgamated to optimize a succinct validity bridging scheme.



## 2024/996

* Title: Great-LaKeys: An Improved Threshold-PRF and a Novel Exponent-VRF from LWR
* Authors: Matthias Geihs
* [Permalink](https://eprint.iacr.org/2024/996)
* [Download](https://eprint.iacr.org/2024/996.pdf)

### Abstract

Building on the recently proposed LWR-based threshold-PRF LaKey, we propose two new constructions. First, we propose an optimized threshold-PRF with significantly reduced round and communication complexity. We achieve this by improving the underlying bit
truncation protocol, as well as the lower bound on the required number of LWR instances. Second, we show that the same underlying PRF construction lends itself as a basis for a novel and efficient exponent-VRF. We implement prototypes of both of our
contributions and demonstrate their practical performance.



## 2024/997

* Title: Dishonest Majority Multi-Verifier Zero-Knowledge Proofs for Any Constant Fraction of Corrupted Verifiers
* Authors: Daniel Escudero, Antigoni Polychroniadou, Yifan Song, Chenkai Weng
* [Permalink](https://eprint.iacr.org/2024/997)
* [Download](https://eprint.iacr.org/2024/997.pdf)

### Abstract

In this work we study the efficiency of Zero-Knowledge (ZK) arguments of knowledge, particularly exploring Multi-Verifier ZK (MVZK) protocols as a midway point between Non-Interactive ZK and Designated-Verifier ZK, offering versatile applications across
various domains. We introduce a new MVZK protocol designed for the preprocessing model, allowing any constant fraction of verifiers to be corrupted, potentially colluding with the prover. Our contributions include the first MVZK over rings. Unlike recent
prior works on fields in the dishonest majority case, our protocol demonstrates communication complexity independent of the number of verifiers, contrasting the linear complexity of previous approaches. This key advancement ensures improved scalability
and efficiency. We provide an end-to-end implementation of our protocol. The benchmark shows that it achieves a throughput of 1.47 million gates per second for 64 verifiers with $50\%$ corruption, and 0.88 million gates per second with $75\%$ corruption.



## 2024/998

* Title: Measuring Conditional Anonymity - A Global Study
* Authors: Pascal Berrang, Paul Gerhart, Dominique Schröder
* [Permalink](https://eprint.iacr.org/2024/998)
* [Download](https://eprint.iacr.org/2024/998.pdf)

### Abstract

The realm of digital health is experiencing a global surge, with mobile applications extending their reach into various facets of daily life. From tracking daily eating habits and vital functions to monitoring sleep patterns and even the menstrual cycle,
these apps have become ubiquitous in their pursuit of comprehensive health insights.
Many of these apps collect sensitive data and promise users to protect their privacy - often through pseudonymization. We analyze the real anonymity that users can expect by this approach and report on our findings. More concretely:

1. We introduce the notion of conditional anonymity sets derived from statistical properties of the population.
2. We measure anonymity sets for two real-world applications and present overarching findings from 39 countries.
3. We develop a graphical tool for people to explore their own anonymity set.

One of our case studies is a popular app for tracking the menstruation cycle. Our findings for this app show that, despite their promise to protect privacy, the collected data can be used to identify users up to groups of 5 people in 97% of all the US
counties, allowing the de-anonymization of the individuals. Given that the US Supreme Court recently overturned abortion rights, the possibility
of determining individuals is a calamity.



## 2024/999

* Title: ProxCode: Efficient Biometric Proximity Searchable Encryption from Error Correcting Codes
* Authors: Maryam Rezapour, Benjamin Fuller
* [Permalink](https://eprint.iacr.org/2024/999)
* [Download](https://eprint.iacr.org/2024/999.pdf)

### Abstract

This work builds approximate proximity searchable encryption. Secure biometric databases are the primary application. Prior work (Kuzu, Islam, and Kantarcioglu, ICDE 2012) combines locality-sensitive hashes, or LSHs, (Indyk, STOC ’98), and oblivious
multimaps. The multimap associates LSH outputs as keywords to biometrics as values.

When the desired result set is of size at most one, we show a new preprocessing technique and system called ProxCode that inserts shares of a linear secret sharing into the map instead of the full biometric. Instead of choosing shares independently,
shares are correlated so exactly one share is associated with each keyword/LSH output. As a result, one can rely on a map instead of a multimap. Secure maps are easier to construct with low leakage than multimaps.

For many parameters, this approach reduces the required number of LSHs for a fixed accuracy. Our scheme yields the most improvement when combining a high accuracy requirement with a biometric with large underlying noise. Our approach builds on any secure
map. We evaluate the scheme accuracy for both iris data and random data.



## 2024/1000

* Title: File-Injection Attacks on Searchable Encryption, Based on Binomial Structures
* Authors: Tjard Langhout, Huanhuan Chen, Kaitai Liang
* [Permalink](https://eprint.iacr.org/2024/1000)
* [Download](https://eprint.iacr.org/2024/1000.pdf)

### Abstract

One distinguishable feature of file-inject attacks on searchable encryption schemes is the 100% query recovery rate, i.e., confirming the corresponding keyword for each query. The main efficiency consideration of file-injection attacks is the number of
injected files. In the work of Zhang et al. (USENIX 2016), $|\log_2|K||$ injected files are required, each of which contains $|K|/2$ keywords for the keyword set $K$. Based on the construction of the uniform $(s,n)$-set, Wang et al. need fewer injected
files when considering the threshold countermeasure. In this work, we propose a new attack that further reduces the number of injected files where Wang et al. need up to 38% more injections to achieve the same results. The attack is based on an increment
$(s,n)$-set, which is also defined in this paper.



## 2024/1001

* Title: Guidance for Efficient Selection of Secure Parameters for Fully Homomorphic Encryption
* Authors: Elena Kirshanova, Chiara Marcolla, Sergi Rovira
* [Permalink](https://eprint.iacr.org/2024/1001)
* [Download](https://eprint.iacr.org/2024/1001.pdf)

### Abstract

The field of Fully Homomorphic Encryption (FHE) has seen many theoretical and computational advances in recent years, bringing the technology closer to practicality than ever before. For this reason, practitioners from neighbouring fields such as machine
learning have sought to understand FHE to provide privacy to their work. Unfortunately, selecting secure and efficient parameters in FHE is a daunting task due to the many interdependencies between the parameters involved. In this work, we solve this
problem by moving away from the standard parameter selection procedure, introducing formulas which provide secure and optimal parameters for any lattice-based scheme. We build our formulas from a strong theoretical foundation based on cryptanalysis
against LWE.



## 2024/1002

* Title: Elementary Formulas for Greatest Common Divisors and Semiprime Factors * Authors: Joseph M. Shunia
* [Permalink](https://eprint.iacr.org/2024/1002)
* [Download](https://eprint.iacr.org/2024/1002.pdf)

### Abstract

We present new formulas for computing greatest common divisors (GCDs) and extracting the prime factors of semiprimes using only elementary arithmetic operations: addition, subtraction, multiplication, floored division, and exponentiation. Our GCD formula
simplifies a result of Mazzanti, and is derived using Kronecker substitution techniques from our previous work. We utilize the GCD formula, along with recent developments on arithmetic terms for square roots and factorials, to derive explicit expressions
for the prime factors of a semiprime $n=pq$.



## 2024/1003

* Title: zkVoting : Zero-knowledge proof based coercion-resistant and E2E verifiable e-voting system
* Authors: Seongho Park, Jaekyoung Choi, Jihye Kim, Hyunok Oh
* [Permalink](https://eprint.iacr.org/2024/1003)
* [Download](https://eprint.iacr.org/2024/1003.pdf)

### Abstract

We introduce ${zkVoting}$, a coercion-resistant e-voting system that utilizes a fake keys approach based on a novel nullifiable commitment scheme. This scheme allows voters to receive both real and fake commitment keys from a registrar. Each ballot
includes this commitment, but only the tallier can efficiently discern the fake ballots, simplifying the tally process to $\mathcal{O}(n)$ and ensuring coercion resistance. ${zkVoting}$ also preserves voter anonymity by ensuring each ballot conceals the
voter's identity. Additionally, by integrating zero-knowledge proofs, ${zkVoting}$ achieves end-to-end (E2E) verifiability. We formally prove its security and demonstrate its practicality for real-world applications, with a ballot casting time of 2.3
seconds and a tally time of 3.9 milliseconds per ballot.



## 2024/1004

* Title: Relaxed Vector Commitment for Shorter Signatures
* Authors: Seongkwang Kim, Byeonghak Lee, Mincheol Son
* [Permalink](https://eprint.iacr.org/2024/1004)
* [Download](https://eprint.iacr.org/2024/1004.pdf)

### Abstract

The MPC-in-the-Head (MPCitH) paradigm has recently gained traction as a foundation for post-quantum signature schemes, offering robust security without the need for trapdoors. Despite its strong security profile, MPCitH-based schemes suffer from high
computational overhead and large signature sizes, limiting their practical application.

This work addresses these inefficiencies by enhancing vector commitments within MPCitH-based schemes. We introduce the concept of vector semi-commitment, which relaxes traditional vector commitment requirements without compromising security, thus
reducing signature size while maintaining performance. We instantiate vector semi-commitment schemes in both the random oracle model and the ideal cipher model, leveraging recent optimizations such as the Half-tree technique. Additionally, we propose a
key injection technique that further minimizes signature size by embedding the secret key into the Half-GGM tree.

We apply these improvements to the BN++ signature scheme and prove it fully secure in the ideal cipher model. Implementing these improvements in the $\mathsf{AIMer}$ v2.0 signature scheme, we achieve up to 18% shorter signatures and up to 112% faster
signing and verification speeds, setting new benchmarks for MPCitH-based schemes.



## 2024/1005

* Title: Differential Fault Attack on HE-Friendly Stream Ciphers: Masta, Pasta and Elisabeth
* Authors: Weizhe Wang, Deng Tang
* [Permalink](https://eprint.iacr.org/2024/1005)
* [Download](https://eprint.iacr.org/2024/1005.pdf)

### Abstract

In this paper, we propose the Differential Fault Attack (DFA) on three Homomorphic Encryption (HE) friendly stream ciphers Masta, Pasta, and Elisabeth. Both Masta and Pasta are Rasta-like ciphers with publicly derived and pseudorandom affine layers. The
design of Elisabeth is an extension of FLIP and FiLIP, following the group filter permutator paradigm. All these three ciphers operate on elements over $\mathbb{Z}_p$ or $\mathbb{Z}_{2^n}$, rather than $\mathbb{Z}_2$. We can recover the secret keys of
all the targeted ciphers through DFA. In particular, for Elisabeth, we present a new method to determine the filtering path, which is vital to make the attack practical. Our attacks on various instances of Masta are practical and require only one block
of keystream and a single word-based fault. By injecting three word-based faults, we can theoretically mount DFA on two instances of Pasta, Pasta-3 and Pasta-4. For our DFA on Elisabeth-4, the only instance of the Elisabeth family, a single bit-based
fault injection is needed. With 15000 normal and faulty keystream words, the DFA on Elisabeth-4 can be completed within several minutes.



## 2024/1006

* Title: Delegated-Query Oblivious Transfer and its Practical Applications
* Authors: Yvo Desmedt, Aydin Abadi
* [Permalink](https://eprint.iacr.org/2024/1006)
* [Download](https://eprint.iacr.org/2024/1006.pdf)

### Abstract

Databases play a pivotal role in the contemporary World Wide Web and the world of cloud computing. Unfortunately, numerous privacy violations have recently garnered attention in the news. To enhance database privacy, we consider Oblivious Transfer (OT),
an elegant cryptographic technology. Our observation reveals that existing research in this domain primarily concentrates on theoretical cryptographic applications, overlooking various practical aspects:

- OTs assume parties have direct access to databases. Our "1-out-of-2 Delegated-Query OT" enables parties to privately query a database, without direct access.

- With the rise of cloud computing, physically separated databases may no longer remain so. Our "1-out-of-2 Delegated-Query Multi-Receiver OT" protects privacy in such evolving scenarios.

- Research often ignores the limitations of thin clients, e.g., Internet of Things devices. To address this, we propose a compiler that transforms any 1-out-of-n OT into a thin client version.



## 2024/1007

* Title: On the vector subspaces of $\mathbb{F}_{2^n}$ over which the multiplicative inverse function sums to zero
* Authors: Claude Carlet
* [Permalink](https://eprint.iacr.org/2024/1007)
* [Download](https://eprint.iacr.org/2024/1007.pdf)

### Abstract

We study the behavior of the multiplicative inverse function (which plays an important role in cryptography and in the study of finite fields), with respect to a recently introduced generalization of almost perfect nonlinearity (APN), called $k$th-order
sum-freedom, that extends a classical characterization of APN functions, and has also some relationship with integral attacks. This generalization corresponds to the fact that a vectorial function $F:\mathbb F_2^n\mapsto \mathbb F_2^m$ sums to a nonzero
value over every $k$-dimensional affine subspace of $\mathbb F_2^n$, for some $k\leq n$. The sum of the values of the inverse function $x\in \mathbb F_{2^n}\mapsto x^{2^n-2}\in \mathbb F_{2^n}$ over any affine subspace $A$ of $\mathbb{F}_{2^n}$ not
containing 0 (i.e. being not a vector space) is easy to address: there exists a simple expression of such sum which shows that it never vanishes. We study in the present paper the case of a vector subspace (a linear subspace), which is much less simple
to handle. We show that the sum depends on a coefficient in subspace polynomials. We derive several expressions of this coefficient. Then we study for which values of $k$ the multiplicative inverse function can sum to nonzero values over all $k$-
dimensional vector subspaces. We show that, for every $k$ not co-prime with $n$, it sums to zero over at least one $k$-dimensional $\mathbb{F}_2$-subspace of $\mathbb{F}_{2^n}$. We study the behavior of the inverse function over direct sums of vector
spaces and we deduce that the property of the inverse function to be $k$th-order sum-free happens for $k$ if and only if it happens for $n-k$. We derive several results on the sums of values of the inverse function over vector subspaces, addressing in
particular the cases of dimension at most 3 (equivalently, of co-dimension at most 3). We leave other cases open and provide computer investigation results.



## 2024/1008

* Title: A Deep Study of The Impossible Boomerang Distinguishers: New Construction Theory and Automatic Search Methods
* Authors: Xichao Hu, Dengguo Feng, Lin Jiao, Yonglin Hao, Xinxin Gong, Yongqiang Li
* [Permalink](https://eprint.iacr.org/2024/1008)
* [Download](https://eprint.iacr.org/2024/1008.pdf)

### Abstract

The impossible boomerang attack (IBA) is a combination of the impossible differential attack and boomerang attack, which has demonstrated remarkable power in the security evaluation of AES and other block ciphers. However, this method has not received
sufficient attention in the field of symmetric cipher analysis. The only existing search method for impossible boomerang distinguishers (IBD), the core of IBAs, is the $\mathcal{UB}\text{-method}$, but it is considered rather rudimentary given current
technological advancements and may result in missed opportunities for effective attacks. Therefore, this paper delves into a comprehensive study on the construction theory and automatic search method of IBDs.

Theoretically, we propose 5 IBD constructions aligned with the techniques of arbitrary S-box, boomerang distinguisher, Boomerang Connectivity Table, U/L/EBCT and mixed tables for differential propagation for SPN-network block ciphers, and 2 IBD
constructions accompanied by state propagation for block ciphers with any structure. Furthermore, we investigate the relationship among these IBD constructions and demonstrate that the most superior IBD aligns precisely with the original definition.
Technically, we develop a general SAT-based automatic search tool for IBDs by introducing optimized search strategies of the composite model method and the mixed model method. This tool not only considers the details of each operation but also takes into
account the impact of key schedule in a single-key setting.

As applications, we first acquire 59584 4-round 1 active word truncated IBDs for AES-128, and 192 of those IBDs cannot be detected by the $\mathcal{UB} \text{-method}$. For Midori64, we first demonstrate the non-existence of $7$-round $1$ active word
truncated IBDs, and obtain $7296$ $6$-round $1$ active word truncated IBDs, which is complementary to the finding that there are no existing $6$-round $1$ active word truncated IDs. For PRESENT-80, we get the first 6-round IBDs which cannot be detected
by the $\mathcal{UB}\text{-method}$. Those results indicate that our method outperforms the $\mathcal{UB}\text{-method}$ and offer an advantage over IDs. We believe that our work can bring new insights to symmetric cipher analysis.



## 2024/1009

* Title: Improved Reductions from Noisy to Bounded and Probing Leakages via Hockey-Stick Divergences
* Authors: Maciej Obremski, João Ribeiro, Lawrence Roy, François-Xavier Standaert, Daniele Venturi
* [Permalink](https://eprint.iacr.org/2024/1009)
* [Download](https://eprint.iacr.org/2024/1009.pdf)

### Abstract

There exists a mismatch between the theory and practice of cryptography in the presence of leakage. On the theoretical front, the bounded leakage model, where the adversary learns bounded-length but noiseless information about secret components, and the
random probing model, where the adversary learns some internal values of a leaking implementation with some probability, are convenient abstractions to analyze the security of numerous designs. On the practical front, side-channel attacks produce long
transcripts which are inherently noisy but provide information about all internal computations, and this noisiness is usually evaluated with closely related metrics like the mutual information or statistical distance. Ideally, we would like to claim that
resilience to bounded leakage or random probing implies resilience to noisy leakage evaluated according to these metrics. However, prior work (Duc, Dziembowski and Faust, Eurocrypt 2014; Brian et al., Eurocrypt 2021) has shown that proving such
reductions with useful parameters is challenging.

In this work, we study noisy leakage models stemming from hockey-stick divergences, which generalize statistical distance and are also the basis of differential privacy. First, we show that resilience to bounded leakage and random probing implies
resilience to our new noisy leakage model with improved parameters compared to models based on the statistical distance or mutual information. Second, we establish composition theorems for our model, showing that these connections extend to a setting
where multiple leakages are obtained from a leaking implementation. We complement our theoretical results with a discussion of practical relevance, highlighting that (i) the reduction to bounded leakage applies to realistic leakage functions with noise
levels that are decreased by several orders of magnitude compared to Brian et al., and (ii) the reduction to random probing usefully generalizes the seminal work of Duc, Dziembowski, and Faust, although it remains limited when the field size in which
masking operates grows (i.e., hockey-stick divergences can better hide the field size dependency of the noise requirements, but do not annihilate it).



## 2024/1010

* Title: FSSiBNN: FSS-based Secure Binarized Neural Network Inference with Free Bitwidth Conversion
* Authors: Peng Yang, Zoe Lin Jiang, Jiehang Zhuang, Junbin Fang, Siu Ming Yiu, Xuan Wang
* [Permalink](https://eprint.iacr.org/2024/1010)
* [Download](https://eprint.iacr.org/2024/1010.pdf)

### Abstract

Neural network inference as a service refers to the process where a cloud server holding a model provides inference services to a client initiating inference requests. Secure neural network inference built on this service ensures the privacy of both the
cloud server's model and the client's data. A binarized neural network (BNN) is a type of neural network with binary weights and activations, expected to accelerate inference. When achieving secure BNN inference using multi-party computation, we must
address the issue of non-uniform bitwidths, i.e., secure computation protocols cannot directly operate on values of different bitwidths and require bitwidth conversion. Existing bitwidth conversion schemes have to expand the bitwidths of weights and
activations, incurring significant communication latency and computational load.

To address the above issues, we propose a secure BNN inference framework, FSSiBNN, with free bitwidth conversion based on function secret sharing (FSS). Specifically, by leveraging the property of FSS that supports arbitrary input and output bitwidths,
we propose a bitwidth conversion embedding scheme. We naturally embed the bitwidth conversion into the FSS-based secure activation and max pooling computation, thereby avoiding the additional computational and communication overhead introduced by the
bitwidth conversion. Moreover, we combine and convert multiple BNN layer functions into fewer matrix multiplication and comparison operations, and precompute multiplication tuples and FSS keys in the offline phase to achieve constant-round online
inference.

In the experiment, we conduct tests on various datasets and models, and compare our results with state-of-the-art work. Compared to the existing best two-party framework XONN (USENIX Security '19), our work is approximately 7$\times$ faster in inference
time and reduces communication overhead by about 577$\times$. Compared with the existing best three-party frameworks, SecureBiNN (ESORICS '22) and FLEXBNN (TIFS '23), our work is approximately 2.5$\times$ faster in inference time and reduces
communication overhead by 1.3 to 16.4$\times$.



## 2024/1011

* Title: Secure Vickrey Auctions with Rational Parties
* Authors: Chaya Ganesh, Shreyas Gupta, Bhavana Kanukurthi, Girisha Shankar
* [Permalink](https://eprint.iacr.org/2024/1011)
* [Download](https://eprint.iacr.org/2024/1011.pdf)

### Abstract

In this work, we construct a second price (Vickrey) auction protocol (SPA), which does not require any auctioneers and ensures total privacy in the presence of rational parties participating in auction. In particular, the confidentiality of the highest
bid and the identity of the second highest bidder are protected. We model the bidders participating in the second price auction as rational, computationally bounded and privacy-sensitive parties. These are self-interested agents who care about winning
the auction more than learning about the private bids of other parties. A rational party does not deviate from the protocol arbitrarily but does so only for its own individual `advantage' -- without any consideration for others. Such an advantage is
modeled using suitable utility functions.

We show that for rational and computationally bounded parties participating in our second-price auctions protocol, there exists a privacy-preserving dominant strategy equilibrium in which every party prefers to follow the protocol rather than to deviate.

Our protocol is implemented using open-source cryptographic constructs. Running our SPA protocol on commodity hardware with $15$ bidders, with bids of length $10$ bits, completes in $1.26$sec and has total communication of $0.77$MB whereas, under
similar conditions, Atlas (semi-honest) protocol takes $40\%$ more time ($2.11$ sec) and $87\%$ more communication ($6.09$MB).

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)