[continued from previous message]

### Abstract

In aggregation queries, predicate parameters often reveal user intent. Protecting these parameters is critical for user privacy, regardless of whether the database is public or private. While most existing works focus on private data settings, we address
a public data setting where the server has access to the database. Current solutions for this setting either require additional setups (e.g., noncolluding servers, hardware enclaves) or are inefficient for practical workloads. Furthermore, they often do
not support range predicates or boolean combinations commonly seen in real-world use cases.

To address these limitations, we built HADES, a fully homomorphic encryption (FHE) based private aggregation system for public data that supports point, range predicates, and boolean combinations. Our one-round HADES protocol efficiently generates
predicate indicators by leveraging the plaintext form of public data records. It introduces a novel elementwise-mapping operation and an optimized reduction algorithm, achieving latency efficiency within a limited noise budget. Our highly scalable, multi-
threaded implementation improves performance over previous one-round FHE solutions by 204x to 6574x on end-to-end TPC-H queries, reducing aggregation time on 1M records from 15 hours to 38 seconds



## 2024/1700

* Title: Does quantum lattice sieving require quantum RAM?
* Authors: Beomgeun Cho, Minki Hhan, Taehyun Kim, Jeonghoon Lee, Yixin Shen
* [Permalink](https://eprint.iacr.org/2024/1700)
* [Download](https://eprint.iacr.org/2024/1700.pdf)

### Abstract

In this paper, we study the requirement for quantum random access memory (QRAM) in quantum lattice sieving, a fundamental algorithm for lattice-based cryptanalysis.

First, we obtain a lower bound on the cost of quantum lattice sieving with a bounded size QRAM. We do so in a new query model encompassing a wide range of lattice sieving algorithms similar to those in the classical sieving lower bound by Kirshanova and
Laarhoven [CRYPTO 21]. This implies that, under reasonable assumptions, quantum speedups in lattice sieving require the use of QRAM. In particular, no quantum speedup is possible without QRAM.

Second, we investigate the trade-off between the size of QRAM and the quantum speedup. We obtain a new interpolation between classical and quantum lattice sieving. Moreover, we show that further improvements require a novel way to use the QRAM by proving
the optimality of some subroutines. An important caveat is that this trade-off requires a strong assumption on the efficient replacement of QRAM data, indicating that even speedups with a small QRAM are already challenging.

Finally, we provide a circuit for quantum lattice sieving without using QRAM. Our circuit has a better depth complexity than the best classical algorithms but requires an exponential amount of qubits. To the best of our knowledge, this is the first
quantum speedup for lattice sieving without QRAM in the standard quantum circuit model. We explain why this circuit does not contradict our lower bound, which considers the query complexity.



## 2024/1701

* Title: Secure Computation with Parallel Calls to 2-ary Functions
* Authors: Varun Narayanan, Shubham Vivek Pawar, Akshayaram Srinivasan
* [Permalink](https://eprint.iacr.org/2024/1701)
* [Download](https://eprint.iacr.org/2024/1701.pdf)

### Abstract

Reductions are the workhorses of cryptography. They allow constructions of complex cryptographic primitives from simple building blocks. A prominent example is the non-interactive reduction from securely computing a ``complex" function $f$ to securely
computing a ``simple" function $g$ via randomized encodings.

Prior work equated simplicity with functions of small degree. In this work, we consider a different notion of simplicity where we require $g$ to only take inputs from a small number of parties. In other words, we want the arity of $g$ to be as small
as possible.

In more detail, we consider the problem of reducing secure computation of arbitrary functions to secure computation of functions with arity two (two is the minimal arity required to compute non-trivial functions). Specifically, we want to compute a
function $f$ via a protocol that makes parallel calls to 2-ary functions. We want this protocol to be secure against malicious adversaries that could corrupt an arbitrary number of parties. We obtain the following results:

- Negative Result: We show that there exists a degree-2 polynomial $p$ such that no protocol that makes parallel calls to 2-ary functions can compute $p$ with statistical security with abort.

- Positive Results: We give two ways to bypass the above impossibility result.

1. Weakening the Security Notion. We show that every degree-2 polynomial can be computed with statistical privacy with knowledge of outputs (PwKO) by making parallel calls to 2-ary functions. Privacy with knowledge of outputs is weaker than security
with abort.

2. Computational Security. We prove that for every function $f$, there exists a protocol for computing $f$ that makes parallel calls to 2-ary functions and achieves security with abort against computationally-bounded adversaries. The security of this
protocol relies on the existence of semi-honest secure oblivious transfer.

- Applications: We give connections between this problem and the task of reducing the encoding complexity of Multiparty Randomized Encodings (MPRE) (Applebaum, Brakerski, and Tsabary, TCC 2018). Specifically, we show that under standard computational
assumptions, there exists an MPRE where the encoder can be implemented by an $\mathrm{NC}^0$ circuit with constant fan-out.

- Extensions: We explore this problem in the honest majority setting and give similar results assuming one-way functions. We also show that if the parties have access to 3-ary functions then we can construct a computationally secure protocol in the
dishonest majority setting assuming one-way functions.



## 2024/1702

* Title: Secure and efficient transciphering for FHE-based MPC
* Authors: Diego F. Aranha, Antonio Guimarães, Clément Hoffmann, Pierrick Méaux
* [Permalink](https://eprint.iacr.org/2024/1702)
* [Download](https://eprint.iacr.org/2024/1702.pdf)

### Abstract

Transciphering (or Hybrid-Homomorphic Encryption, HHE) is an es-
tablished technique for avoiding ciphertext expansion in HE applications, saving communication and storage resources. Recently, it has also been shown to be a fundamental component in the practical construction of HE-based multi-party computation (MPC)
protocols, being used both for input data and intermediary results (Smart, IMACC 2023). In these protocols, however, ciphers are used with keys that are jointly generated by multiple (possibly malicious) parties, which may require additional security
assumptions that have been so far overlooked in the HHE literature. In this paper, we formalize this issue as a security against related-key attacks (RKA) problem and provide efficient solutions for it. We start by presenting an efficient method for
homomorphically evaluating Mixed-Filter-Permutator (MFP) ciphers in leveled mode, enabling speedups of up to thousands of times compared to previous literature. For the multi-party scenario, we focus specifically on the Margrethe cipher (Hoffmann et al.,
INDOCRYPT 2023). We show that, contrary to other commonly used HHE ciphers (e.g. FLIP), Margrethe is out-of-the-box secure for any protocols that allow malicious parties to learn up to two related key streams, enabling security for the vast majority of
static MPC protocols. For other cases, we quantify the loss of security based on the number of related key streams (which often depends on the number of malicious parties and specific protocol). Performance-wise, our implementation of Margrethe takes
just 3.9 ms to transcipher 4 bit messages, being significantly faster than the state of the art in terms of latency.



## 2024/1703

* Title: Free-XOR Gate Bootstrapping
* Authors: Chunling Chen, Xianhui Lu, Ruida Wang, Zhihao Li, Xuan Shen, Benqiang Wei
* [Permalink](https://eprint.iacr.org/2024/1703)
* [Download](https://eprint.iacr.org/2024/1703.pdf)

### Abstract

The FHEW-like gate bootstrapping framework operates in a 2-bit plaintext space, where logic gates such as NAND, XOR, and AND are implemented by adding two ciphertexts and extracting the most significant bit. However, each gate operation requires
bootstrapping with a primary cost of one blind rotation, which is expensive, when processing circuit operations for applications. We propose a novel Free-XOR gate bootstrapping framework based on a single-bit plaintext space, in which the XOR operation
is realized by simply adding two ciphertexts, resulting in an almost free computational cost. To form a minimal complete set for logical operations, we design an algorithm for the AND gate within this framework. The AND gate cost of our Free-XOR gate
bootstrapping involves two blind rotations. However, by utilizing a single-bit plaintext space to enhance noise tolerance and swapping some operations of the bootstrapping process, we can adopt a more compact parameter setting, which in turn accelerates
the speed of blind rotation. We propose an instantiation of the NTRU-based AND gate operation, which requires two blind rotations. Despite the additional rotation, the overall computational cost is marginally lower than the state-of-the-art gate
bootstrapping scheme LLW+ [TCHES24], which utilizes only a single blind rotation. In addition, our approach achieves a significant reduction in key size, reducing it to 3.3 times the size of LLW+ [TCHES24].



## 2024/1704

* Title: From One-Time to Two-Round Reusable Multi-Signatures without Nested Forking
* Authors: Lior Rotem, Gil Segev, Eylon Yogev
* [Permalink](https://eprint.iacr.org/2024/1704)
* [Download](https://eprint.iacr.org/2024/1704.pdf)

### Abstract

Multi-signature schemes are gaining significant interest due to their blockchain applications. Of particular interest are two-round schemes in the plain public-key model that offer key aggregation, and whose security is based on the hardness of the DLOG
problem. Unfortunately, despite substantial recent progress, the security proofs of the proposed schemes provide rather insufficient concrete guarantees (especially for 256-bit groups). This frustrating situation has so far been approached either by
relying on the security of seemingly stronger assumptions or by considering restricted classes of attackers (e.g., algebraic attackers, which are assumed to provide an algebraic justification of each group element that they produce).

We present a complementing approach by constructing multi-signature schemes that satisfy two relaxed notions of security, whose applicability nevertheless ranges from serving as drop-in replacements to enabling expressive smart contract validation
procedures. Our first notion, one-time unforgeability, extends the analogous single-signer notion by considering attackers that obtain a single signature for some message and set of signers of their choice. We construct a non-interactive one-time scheme
based on any ring-homomorphic one-way function, admitting efficient instantiations based on the DLOG and RSA assumptions. Aggregated verification keys and signatures consist of two group elements and a single group element, respectively, and our security
proof consists of a single application of the forking lemma (thus avoiding the substantial security loss exhibited by the proposed two-round schemes). Additionally, we demonstrate that our scheme naturally extends to a $t$-time scheme, where aggregated
verification keys consist of $t+1$ group elements, while aggregated signatures still consist of a single group element.

Our second notion, single-set unforgeability, considers attackers that obtain any polynomial number of signatures but are restricted to a single set of signers of their choice. We transform any non-interactive one-time scheme into a two-round single-set
scheme via a novel forking-free construction that extends the seminal Naor-Yung tree-based approach to the multi-signer setting. Aggregated verification keys are essentially identical to those of the underlying one-time scheme, and the length of
aggregated signatures is determined by that of the underlying scheme while scaling linearly with the length of messages (noting that long messages can always be hashed using a collision-resistant function). Instantiated with our one-time scheme, we
obtain aggregated verification keys and signatures whose lengths are completely independent of the number of signers.



## 2024/1705

* Title: Dumbo-MPC: Efficient Fully Asynchronous MPC with Optimal Resilience
* Authors: Yuan Su, Yuan Lu, Jiliang Li, Yuyi Wang, Chengyi Dong, Qiang Tang
* [Permalink](https://eprint.iacr.org/2024/1705)
* [Download](https://eprint.iacr.org/2024/1705.pdf)

### Abstract

Fully asynchronous multi-party computation (AMPC) has superior robustness in realizing privacy and guaranteed output delivery (G.O.D.) against asynchronous adversaries that can arbitrarily delay communications. However, none of these protocols are truly
practical, as they either have sub-optimal resilience, incur cumbersome communication cost, or suffer from an online phase with extra cryptographic overhead. The only attempting implementation---HoneyBadgerMPC (hbMPC)---merely ensures G.O.D. in some
implausible optimistic cases due to a non-robust offline pre-processing phase.

We propose Dumbo-MPC a concretely efficient AMPC-as-a-service design with all phases G.O.D. and optimal resilience against $t<n/3$ malicious parties (where $n$ is the total number of parties). Same to hbMPC, Dumbo-MPC has a robust (almost) information-
theoretic online phase that can efficiently perform online computations, given pre-processed multiplication triples. While for achieving all phases G.O.D., we design a novel dual-mode offline protocol that can robustly pre-process multiplication triples
in asynchrony. The offline phase features $O(n)$ per-triple communication in the optimistic case, followed by a fully asynchronous fallback to a pessimistic path to securely restore G.O.D. in the bad case. To efficiently implement the pessimistic path,
we devise a concretely efficient zk-proof for product relationship of secret shares over compact KZG polynomial commitments, which enables us to reduce the degree of two secret shares' product from $2t$ to $t$ and could be of independent interest.

We also implement and extensively evaluate Dumbo-MPC (particularly its offline phase) in varying network settings with up to 31 AWS servers. To our knowledge, we provide the first implementation of AMPC with all-phase G.O.D. A recent asynchronous triple
generation protocol from Groth and Shoup (GS23) is also implemented and experimentally compared. When $n = 31$, Dumbo-MPC generates 94 triples/sec (almost twice of GS23) in the pessimistic case and 349 triples/sec (6X of GS23) in the good case, such that
31 parties require only 2-8 min to prepare a private Vickrey auction of 100 bidders or 10-36 min for a mixing network of $2^{10}$ inputs.



## 2024/1706

* Title: State of the art of HFE variants Is it possible to repair HFE with appropriate perturbations?
* Authors: Benoit COGLIATI, Gilles Macariot-Rat, Jacques Patarin, Pierre Varjabedian
* [Permalink](https://eprint.iacr.org/2024/1706)
* [Download](https://eprint.iacr.org/2024/1706.pdf)

### Abstract

HFE (that stands for Hidden Field Equations) belongs to
multivariate cryptography and was designed by Jacques Patarin in 1996
as a public key trapdoor suitable for encryption or signature. This original basic version is unfortunately known to have a super-polynomial
attack, but as imagined since the beginning, it comes with various variants, one can describe as combinations of “modifiers”.
In this work, we first present the state of the art of these HFE modifiers, along with their effect on the complexity of the main cryptanalysis techniques against HFE-based schemes. This allows us, in a second time, to
identify a combination of two modifiers that has not yet been explored
and may still be secure with efficient parameters. Based on our analysis,
we propose a new signature scheme that offers extremely short signature
sizes, with reasonable public key sizes and performance. In particular, we
rely on the classical Feistel-Patarin technique to reduce signature sizes
below two times the security parameter.



## 2024/1707

* Title: CountCrypt: Quantum Cryptography between QCMA and PP
* Authors: Eli Goldin, Tomoyuki Morimae, Saachi Mutreja, Takashi Yamakawa
* [Permalink](https://eprint.iacr.org/2024/1707)
* [Download](https://eprint.iacr.org/2024/1707.pdf)

### Abstract

We construct a quantum oracle relative to which $\mathbf{BQP}=\mathbf{QCMA}$ but quantum-computation-classical-communication (QCCC) key exchange, QCCC commitments, and two-round quantum key distribution exist. We also construct an oracle relative to
which $\mathbf{BQP}=\mathbf{QMA}$, but quantum lightning (a stronger variant of quantum money) exists. This extends previous work by Kretschmer [Kretschmer, TQC22], which showed that there is a quantum oracle relative to which $\mathbf{BQP}=\mathbf{QMA}$
but pseudorandom state generators (a quantum variant of pseudorandom generators) exist.
We also show that QCCC key exchange, QCCC commitments, and two-round quantum key distribution can all be used to build one-way puzzles. One-way puzzles are a version of "quantum samplable" one-wayness and are an intermediate primitive between
pseudorandom state generators and EFI pairs, the minimal quantum primitive. In particular, one-way puzzles cannot exist if $\mathbf{BQP}=\mathbf{PP}$.
Our results together imply that aside from pseudorandom state generators, there is a large class of quantum cryptographic primitives which can exist even if $\mathbf{BQP} = \mathbf{QCMA}$, but are broken if $\mathbf{BQP} = \mathbf{PP}$. Furthermore,
one-way puzzles are a minimal primitive for this class. We denote this class "CountCrypt".



## 2024/1708

* Title: Subliminal Encrypted Multi-Maps and Black-Box Leakage Absorption
* Authors: Amine Bahi, Seny Kamara, Tarik Moataz, Guevara Noubir
* [Permalink](https://eprint.iacr.org/2024/1708)
* [Download](https://eprint.iacr.org/2024/1708.pdf)

### Abstract

We propose a dynamic, low-latency encrypted multi-map (EMM) that operates in two
modes: low-leakage mode, which reveals minimal information such as data
size, expected response length, and query arrival rate; and subliminal
mode, which reveals only the data size while hiding metadata including query and update times, the number of operations executed, and even whether an operation was executed at all---albeit at the cost of full correctness. We achieve this by exploiting a tradeoff between leakage and latency, a previously underexplored resource in EMM design. In low-leakage mode, our construction improves upon existing work both asymptotically and empirically: it achieves optimal server-side storage, as well as communication and computational complexity that is independent of the maximum response length. In subliminal mode, it is the first construction to hide metadata.

To analyze the latency and client-side storage of our construction, we utilize queuing theory and introduce a new queuing model, which may be of independent interest. To examine its metadata-hiding properties, we extend standard security definitions to
account for metadata and prove a surprising result: if a scheme is subliminal in that it hides the execution of its operations, then it absorbs the leakage of any scheme that makes black-box use of it without sending additional messages. In other words,
if a scheme is subliminal, then any scheme that makes black-box use of it will also be subliminal.

We implement and evaluate our construction, demonstrating that our empirical results align with our theoretical analysis and that the scheme achieves a median query latency below $10$ milliseconds, making it practical for some applications.



## 2024/1709

* Title: Do Not Disturb a Sleeping Falcon: Floating-Point Error Sensitivity of the Falcon Sampler and Its Consequences
* Authors: Xiuhan Lin, Mehdi Tibouchi, Yang Yu, Shiduo Zhang
* [Permalink](https://eprint.iacr.org/2024/1709)
* [Download](https://eprint.iacr.org/2024/1709.pdf)

### Abstract

Falcon is one of the three postquantum signature schemes already selected by NIST for standardization. It is the most compact among them, and offers excellent efficiency and security. However, it is based on a complex algorithm for lattice discrete
Gaussian sampling which presents a number of implementation challenges. In particular, it relies on (possibly emulated) floating-point arithmetic, which is often regarded as a cause for concern, and has been leveraged in, e.g., side-channel analysis. The
extent to which Falcon's use of floating point arithmetic can cause security issues has yet to be thoroughly explored in the literature.

In this paper, we contribute to filling this gap by identifying a way in which Falcon's lattice discrete Gaussian sampler, due to specific design choices, is singularly sensitive to floating-point errors. In the presence of small floating-point
discrepancies (which can occur in various ways, including the use of the two almost but not quite equivalent signing procedures ``dynamic'' and ``tree'' exposed by the Falcon API), we find that, when called twice on the same input, the Falcon sampler
has a small but significant chance (on the order of once in a few thousand calls) of outputting two different lattice points with a very structured difference, that immediately reveals the secret key. This is in contrast to other lattice Gaussian
sampling algorithms like Peikert's sampler and Prest's hybrid sampler, that are stable with respect to small floating-point errors.

Correctly generated Falcon signatures include a salt that should in principle prevent the sampler to ever be called on the same input twice. In that sense, our observation has little impact on the security of Falcon signatures per se (beyond echoing
warnings about the dangers of repeated randomness). On the other hand, it is critical for derandomized variants of Falcon, which have been proposed for use in numerous settings. One can mention in particular identity-based encryption, SNARK-friendly
signatures, and sublinear signature aggregation. For all these settings, small floating point discrepancies have a chance of resulting in full private key exposure, even when using the slower, integer-based emulated floating-point arithmetic of Falcon's
reference implementation.



## 2024/1710

* Title: $\widetilde{\mbox{O}}$ptimal Adaptively Secure Hash-based Asynchronous Common Subset
* Authors: Hanwen Feng, Zhenliang Lu, Qiang Tang
* [Permalink](https://eprint.iacr.org/2024/1710)
* [Download](https://eprint.iacr.org/2024/1710.pdf)

### Abstract

Asynchronous multiparty computation (AMPC) requires an input agreement phase where all participants have a consistent view of the set of private inputs. While the input agreement problem can be precisely addressed by a Byzantine fault-tolerant consensus
known as Asynchronous Common Subset (ACS), existing ACS constructions with potential post-quantum security have a large $\widetilde{\mathcal{O}}(n^3)$ communication complexity for a network of $n$ nodes. This poses a bottleneck for AMPC in the same
setting. In contrast, ACS has optimal constructions with quadratic communication complexity based on bilinear map assumptions.

In this paper, we bridge this gap by introducing a nearly optimal ACS, which solely relies on the blackbox use of collision-resistant hash functions. It exhibits $\widetilde{\mathcal{O}}(n^2)$ communication complexity, expected constant round complexity,
and security against adaptive adversaries who can corrupt up to $n/3$ nodes and perform ``after-fact-removal'' attacks.

At the core of our new ACS is the first nearly optimal hash-based Multi-valued Validated Byzantine Agreement (MVBA).
To reduce cubic communication while avoiding heavy cryptographic tools, we introduce a new design paradigm, with several new components. We define and analyze our MVBA and components within the UC-framework, facilitating their modular use in broader
applications, particularly in AMPC.



## 2024/1711

* Title: Good things come to those who wait: Dishonest-Majority Coin-Flipping Requires Delay Functions
* Authors: Joseph Bonneau, Benedikt Bünz, Miranda Christ, Yuval Efron
* [Permalink](https://eprint.iacr.org/2024/1711)
* [Download](https://eprint.iacr.org/2024/1711.pdf)

### Abstract

We reconsider Cleve's famous 1986 impossibility result on coin-flipping without an honest majority. Recently proposed constructions have circumvented this limit by using cryptographic delay functions. We show that this is necessary: a (weak) notion of
delay functions is in fact implied by the existence of a protocol circumventing Cleve's impossibility. However, such delay functions are weaker than those used in existing constructions. We complete our result by showing an equivalence, that these weaker
delay functions are also sufficient to construct not just fair dishonest-majority coin-flipping protocols, but also the stronger notion of a distributed randomness beacon. We also show that this is possible in a weaker communication model than previously
considered, without the assumption of reliable broadcast or a public bulletin board.



## 2024/1712

* Title: Low-Communication Updatable PSI from Asymmetric PSI and PSU
* Authors: Guowei Ling, Peng Tang, Weidong Qiu
* [Permalink](https://eprint.iacr.org/2024/1712)
* [Download](https://eprint.iacr.org/2024/1712.pdf)

### Abstract

Private Set Intersection (PSI) allows two mutually untrusted parties to compute the intersection of their private sets without revealing additional information. In general, PSI operates in a static setting, where the computation is performed only once on
the input sets of both parties. Badrinarayanan et al. (\textit{PoPETs} 2022) initiated the study of Updatable PSI (UPSI), which extends this capability to dynamically updating sets, enabling both parties to securely compute the intersection as their sets
are modified while incurring significantly less overhead than re-executing a conventional PSI. However, existing UPSI protocols either do not support arbitrary deletion of elements or incur high computational and communication overhead. In this work, we
combine asymmetric PSI with Private Set Union (PSU) to present a novel UPSI protocol. Our UPSI protocol supports arbitrary additions and deletions of elements, offering a flexible approach to update sets. Furthermore, our protocol enjoys extremely low
communication overhead, scaling linearly with the size of the update set while remaining independent of the total set size. We implement our protocol and compare it against state-of-the-art conventional PSI and UPSI protocols. Experimental results
demonstrate that our UPSI protocol incurs $587$ to $755$ times less communication overhead than the recently proposed UPSI protocol (\textit{AsiaCrypt} 2024) that supports arbitrary additions and deletions. Moreover, our UPSI protocol has a significant
advantage in low-bandwidth environments due to the exceptionally low communication overhead. Specifically, with an input size of $2^{22}$ and the size of the addition/deletion set being $2^{10}$, the existing UPSI protocol requires approximately $1650.45$
, $1789.5$, and $3458.1$ seconds at bandwidths of $200$ Mbps, $50$ Mbps, and $5$ Mbps, respectively, whereas our UPSI protocol only requires around $13.01$, $13.75$, and $22.53$ seconds under the same conditions. Our open-source implementation is
available at: \href{https://github.com/ShallMate/upsi}{https://github.com/ShallMate/upsi}.



## 2024/1713

* Title: Universally Composable Non-Interactive Zero-Knowledge from Sigma Protocols via a New Straight-line Compiler
* Authors: Megan Chen, Pousali Dey, Chaya Ganesh, Pratyay Mukherjee, Pratik Sarkar, Swagata Sasmal
* [Permalink](https://eprint.iacr.org/2024/1713)
* [Download](https://eprint.iacr.org/2024/1713.pdf)

### Abstract

Non-interactive zero-knowledge proofs (NIZK) are essential building blocks in threshold cryptosystems like multiparty signatures, distributed key generation, and verifiable secret sharing, allowing parties to prove correct behavior without revealing
secrets. Furthermore, universally composable (UC) NIZKs enable seamless composition in the larger cryptosystems. A popular way to construct NIZKs is to compile interactive protocols using the Fiat-Shamir transform. Unfortunately, Fiat-Shamir transformed
NIZK requires rewinding the adversary and is not $\textit{straight-line extractable}$, making it at odds with UC. Using Fischlin's transform gives straight-line extractability, but at the expense of many repetitions of the underlying protocol leading to
poor concrete efficiency and difficulty in setting parameters.

In this work, we propose a simple new transform that compiles a Sigma protocol for an algebraic relation into a UC-NIZK protocol $\textit{without any overheads of repetition}$.

- Given a Sigma protocol for proving m algebraic statements over n witnesses, we construct a compiler to transform it into a $\textit{straight-line extractable}$ protocol using an additively homomorphic encryption scheme AHE. Our prover executes the
Sigma protocol's prover once and computes 2n encryptions. The verification process involves running the Sigma protocol verifier once and then computing n encryptions, which are homomorphically verified against the prover generated encryptions.

- We apply the Fiat-Shamir transform to the above straight-line extractable Sigma protocol to obtain a UC-NIZK. We instantiate AHE using class group-based encryption where the public key of the encryption scheme is obliviously sampled using a
suitable hash function. This yields a UC-NIZK protocol in the random oracle model.



## 2024/1714

* Title: Theoretical Approaches to Solving the Shortest Vector Problem in NP-Hard Lattice-Based Cryptography with Post-SUSY Theories of Quantum Gravity in Polynomial Time
* Authors: Trevor Nestor
* [Permalink](https://eprint.iacr.org/2024/1714)
* [Download](https://eprint.iacr.org/2024/1714.pdf)

### Abstract


[continued in next message]

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