## In this issue

1. [2023/1733] Hintless Single-Server Private Information Retrieval
2. [2024/863] Length Leakage in Oblivious Data Access Mechanisms
3. [2024/880] Extending class group action attacks via pairings
4. [2024/916] Polymath: Groth16 Is Not The Limit
5. [2024/917] Unbounded Non-Zero Inner Product Encryption
6. [2024/918] Cryptographic Analysis of Delta Chat
7. [2024/919] Multi-Input Functional Encryption for Unbounded ...
8. [2024/920] Leveraging Small Message Spaces for CCA1 Security ...
9. [2024/921] Simple Logarithmic-size LSAG signature
10. [2024/922] Scalable Private Set Union, with Stronger Security
11. [2024/923] On Orchestrating Parallel Broadcasts for ...
12. [2024/924] Climbing and descending tall volcanos
13. [2024/925] Time Sharing - A Novel Approach to Low-Latency Masking
14. [2024/926] Verifiable and Private Vote-by-Mail
15. [2024/927] MATHEMATICAL SPECULATIONS ON CRYPTOGRAPHY
16. [2024/928] The Committing Security of MACs with Applications ...
17. [2024/929] Combining Outputs of a Random Permutation: New ...
18. [2024/930] Information-Theoretic Single-Server PIR in the ...
19. [2024/931] Leveled Fully-Homomorphic Signatures from Batch ...
20. [2024/932] CISELeaks: Information Leakage Assessment of ...
21. [2024/933] A Pure Indistinguishability Obfuscation Approach to ...
22. [2024/934] An Explicit High-Moment Forking Lemma and its ...
23. [2024/935] MFKDF: Multiple Factors Knocked Down Flat
24. [2024/936] Willow: Secure Aggregation with One-Shot Clients
25. [2024/937] Distributed Point Function with Constraints, Revisited
26. [2024/938] Certifying Private Probabilistic Mechanisms
27. [2024/939] Two RSA-based Cryptosystems
28. [2024/940] Scalable Collaborative zk-SNARK and Its Application ...
29. [2024/941] SmartZKCP: Towards Practical Data Exchange ...
30. [2024/942] Let Them Drop: Scalable and Efficient Federated ...
31. [2024/943] Dual Polynomial Commitment Schemes and Applications ...
32. [2024/944] Quantum CCA-Secure PKE, Revisited
33. [2024/945] Quantum-Safe Public Key Blinding from MPC-in-the- ...
34. [2024/946] Provably Secure Butterfly Key Expansion from the ...
35. [2024/947] A Modular Approach to Registered ABE for Unbounded ...
36. [2024/948] Return of the Kummer: a toolbox for genus 2 ...
37. [2024/949] Efficient 2PC for Constant Round Secure Equality ...
38. [2024/950] DISCO: Dynamic Searchable Encryption with Constant ...
39. [2024/951] Notes on (failed) attempts to instantiate TLR3
40. [2024/952] Communication Complexity vs Randomness Complexity ...
41. [2024/953] MixBuy: Contingent Payment in the Presence of Coin ...
42. [2024/954] Arithmetisation of computation via polynomial ...
43. [2024/955] ElectionGuard: a Cryptographic Toolkit to Enable ...
44. [2024/956] SNARGs under LWE via Propositional Proofs

## 2023/1733

* Title: Hintless Single-Server Private Information Retrieval
* Authors: Baiyu Li, Daniele Micciancio, Mariana Raykova, Mark Schultz-Wu
* [Permalink](https://eprint.iacr.org/2023/1733)
* [Download](https://eprint.iacr.org/2023/1733.pdf)

### Abstract

We present two new constructions for private information retrieval (PIR) in the classical setting where the clients do not need to do any preprocessing or store any database dependent information, and the server does not need to store any client-
dependent information.

Our first construction (HintlessPIR) eliminates the client preprocessing step from the recent LWE-based SimplePIR (Henzinger et. al., USENIX Security 2023) by outsourcing the "hint" related computation to the server, leveraging a new concept of
homomorphic encryption with composable preprocessing.
We realize this concept with RLWE encryption schemes, and by leveraging the composibility of this technique we are able to preprocess almost all the expensive parts of the homomorphic computation and reuse them across multiple protocol executions.
As a concrete application, we propose highly efficient matrix vector multiplication that allows us to build HintlessPIR. For a database of size 8GB, HintlessPIR achieves throughput about 6.37GB/s without requiring transmission of any client or server
state.
We additionally formalize the matrix vector multiplication protocol as a novel primitive that we call LinPIR, which may be of independent interest.

In our second construction (TensorPIR) we reduce the communication of HintlessPIR from square root to cubic root in the database size.
For this purpose we extend our HE with preprocessing techniques to composition of key-switching keys and the query expansion algorithm.
We show how to use RLWE encryption with preprocessing to outsource LWE decryption for ciphertexts generated by homomorphic multiplications.
This allows the server to do more complex processing using a more compact query under LWE.

We implement and benchmark HintlessPIR which achieves better concrete costs than TensorPIR for a large set of databases of interest.
We show that it improves the communication of recent preprocessing constructions when clients do not have large numbers of queries or the database updates frequently.
The computation cost for removing the hint is small and decreases as the database becomes larger, and it is always more efficient than other constructions with client hints such as Spiral PIR (Menon and Wu, S&P 2022).
In the setting of anonymous queries we also improve on Spiral's communication.



## 2024/863

* Title: Length Leakage in Oblivious Data Access Mechanisms
* Authors: Grace Jia, Rachit Agarwal, Anurag Khandelwal
* [Permalink](https://eprint.iacr.org/2024/863)
* [Download](https://eprint.iacr.org/2024/863.pdf)

### Abstract

This paper explores the problem of preventing length leakage in oblivious data access mechanisms with passive persistent adversaries. We show that designing mechanisms that prevent both length leakage and access pattern leakage requires navigating a
three-way tradeoff between storage footprint, bandwidth footprint, and the information leaked to the adversary. We establish powerful lower bounds on achievable storage and bandwidth footprints for a variety of leakage profiles, and present constructions
that perfectly or near-perfectly match the lower bounds.



## 2024/880

* Title: Extending class group action attacks via pairings
* Authors: Joseph Macula, Katherine E. Stange
* [Permalink](https://eprint.iacr.org/2024/880)
* [Download](https://eprint.iacr.org/2024/880.pdf)

### Abstract

We introduce a new tool for the study of isogeny-based cryptography, namely pairings which are sesquilinear (conjugate linear) with respect to the $\mathcal{O}$-module structure of an elliptic curve with CM by an imaginary quadratic order $\mathcal{O}$.
We use these pairings to study the security of problems based on the class group action on collections of oriented ordinary or supersingular elliptic curves. This extends work of of both (Castryck, Houben, Merz, Mula, Buuren, Vercauteren, 2023) and (De
Feo, Fouotsa, Panny, 2024).



## 2024/916

* Title: Polymath: Groth16 Is Not The Limit
* Authors: Helger Lipmaa
* [Permalink](https://eprint.iacr.org/2024/916)
* [Download](https://eprint.iacr.org/2024/916.pdf)

### Abstract

Shortening the argument (three group elements or 1536 / 3072 bits over the BLS12-381/BLS24-509 curves) of the Groth16 zk-SNARK for R1CS is a long-standing open problem. We propose a zk-SNARK Polymath for the Square Arithmetic Programming constraint
system using the KZG polynomial commitment scheme. Polymath has a shorter argument (1408 / 1792 bits over the same curves) than Groth16. At 192-bit security, Polymath's argument is nearly half the size, making it highly competitive for high-security
future applications. Notably, we handle public inputs in a simple way. We optimized Polymath's prover through an exhaustive parameter search. Polymath's prover does not output $\mathbb{G}_{2}$ elements, aiding in batch verification, SNARK aggregation,
and recursion. Polymath's properties make it highly suitable to be the final SNARK in SNARK compositions.



## 2024/917

* Title: Unbounded Non-Zero Inner Product Encryption
* Authors: Bishnu Charan Behera, Somindu C. Ramanna
* [Permalink](https://eprint.iacr.org/2024/917)
* [Download](https://eprint.iacr.org/2024/917.pdf)

### Abstract

In a non-zero inner product encryption (NIPE) scheme, ciphertexts and keys are associated with vectors from some inner-product space. Decryption of a ciphertext for $\vec{x}$ is allowed by a key for $\vec{y}$ if and only if the inner product $\langle{\
vec{x}},{\vec{y}}\rangle \neq 0$.
Existing constructions of NIPE assume the length of the vectors are fixed apriori.
We present the first constructions of $ unbounded $ non-zero inner product encryption (UNIPE) with constant sized keys. Unbounded here refers to the size of vectors not being pre-fixed during setup. Both constructions, based on bilinear maps, are proven
selectively secure under the decisional bilinear Diffie-Hellman (DBDH) assumption.

Our constructions are obtained by transforming the unbounded inner product functional encryption (IPFE) schemes of Dufour-Sans and Pointcheval (ACNS 2019), one in the $strict ~ domain$ setting and the other in the $permissive ~ domain$ setting.
Interestingly, in the latter case, we prove security from DBDH, a static assumption while the original IPE scheme relied on an interactive parameterised assumption. In terms of efficiency, features of the IPE constructions are retrained after
transformation to NIPE. Notably, the public key and decryption keys have constant size.



## 2024/918

* Title: Cryptographic Analysis of Delta Chat
* Authors: Yuanming Song, Lenka Mareková, Kenneth G. Paterson
* [Permalink](https://eprint.iacr.org/2024/918)
* [Download](https://eprint.iacr.org/2024/918.pdf)

### Abstract

We analyse the cryptographic protocols underlying Delta Chat, a decentralised messaging application which uses e-mail infrastructure for message delivery. It provides end-to-end encryption by implementing the Autocrypt standard and the SecureJoin
protocols, both making use of the OpenPGP standard. Delta Chat's adoption by categories of high-risk users such as journalists and activists, but also more generally users in regions affected by Internet censorship, makes it a target for powerful
adversaries. Yet, the security of its protocols has not been studied to date. We describe five new attacks on Delta Chat in its own threat model, exploiting cross-protocol interactions between its implementation of SecureJoin and Autocrypt, as well as
bugs in rPGP, its OpenPGP library. The findings have been disclosed to the Delta Chat team, who implemented fixes.



## 2024/919

* Title: Multi-Input Functional Encryption for Unbounded Inner Products
* Authors: Bishnu Charan Behera, Somindu C. Ramanna
* [Permalink](https://eprint.iacr.org/2024/919)
* [Download](https://eprint.iacr.org/2024/919.pdf)

### Abstract

In this work, we propose a construction for $ Multi~Input~Inner ~Product ~Encryption$ (MIPFE) that can handle vectors of variable length in different encryption slots. This construction is the first of its kind, as all existing MIPFE schemes allow only
equal length vectors. The scheme is constructed in the private key setting, providing privacy for both message as well as the function, thereby achieving the so-called $full-hiding$ security. Our MIPFE scheme uses bilinear groups of prime order and
achieves security under well studied cryptographic assumptions, namely, the symmetric external Diffie-Hellman assumption.



## 2024/920

* Title: Leveraging Small Message Spaces for CCA1 Security in Additively Homomorphic and BGN-type Encryption
* Authors: Benoit Libert
* [Permalink](https://eprint.iacr.org/2024/920)
* [Download](https://eprint.iacr.org/2024/920.pdf)

### Abstract

We show that the smallness of message spaces can be used as a checksum allowing to hedge against CCA1 attacks in additively homomorphic encryption schemes. We first show that the additively homomorphic variant of Damgård's Elgamal provides IND-CCA1
security under the standard DDH assumption. Earlier proofs either required non-standard assumptions or only applied to hybrid versions of Damgård's Elgamal, which are not additively homomorphic. Our security proof builds on hash proof systems and
exploits the fact that encrypted messages must be contained in a polynomial-size interval in order to enable decryption. With $3$ group elements per ciphertext, this positions Damgård's Elgamal as the most efficient/compact DDH-based additively
homomorphic CCA1 cryptosystem. Under the same assumption, the best candidate so far was the lite Cramer-Shoup cryptosystem, where ciphertexts consist of $4$ group elements. We extend this observation to build an IND-CCA1 variant of the Boneh-Goh-Nissim
encryption scheme, which allows evaluating 2-DNF formulas on encrypted data. By computing tensor products of Damgård's Elgamal ciphertexts, we obtain product ciphertexts consisting of $9$ group elements (instead of $16$ elements if we were tensoring
lite Cramer-Shoup ciphertexts) in the target group of a bilinear map. Using similar ideas, we also obtain a CCA1 variant of the Elgamal-Paillier cryptosystem by forcing $\lambda$ plaintext bits to be zeroes, which yields CCA1 security almost for free. In
particular, the message space remains exponentially large and ciphertexts are as short as in the IND-CPA scheme. We finally adapt the technique to the Castagnos-Laguillaumie system.



## 2024/921

* Title: Simple Logarithmic-size LSAG signature
* Authors: Edsger Hughes
* [Permalink](https://eprint.iacr.org/2024/921)
* [Download](https://eprint.iacr.org/2024/921.pdf)

### Abstract

A number of existing cryptosystems use the well-known LSAG signature and its extensions. This article presents a simple logarithmic-size signature scheme LS-LSAG which, despite a radical reduction in size, retains the basic code block of the LSAG
signature. Therefore, substituting LS-LSAG for LSAG requires minimal changes to almost any existing coded LSAG extension, making it logarithmic instead of linear.



## 2024/922

* Title: Scalable Private Set Union, with Stronger Security
* Authors: Yanxue Jia, Shi-Feng Sun, Hong-Sheng Zhou, Dawu Gu
* [Permalink](https://eprint.iacr.org/2024/922)
* [Download](https://eprint.iacr.org/2024/922.pdf)

### Abstract

Private Set Union (PSU) protocol allows parties, each holding an input set, to jointly compute the union of the sets without revealing anything else. In the literature, scalable PSU protocols follow the “split-execute-assemble” paradigm (Kolesnikov
et al., ASIACRYPT 2019); in addition, those fast protocols often use Oblivious Transfer as building blocks. Kolesnikov et al. (ASIACRYPT 2019) and Jia et al. (USENIX Security 2022), pointed out that certain security issues can be introduced in the “
split-execute-assemble” paradigm. In this work, surprisingly, we observe that the typical way of invoking Oblivious Transfer also causes unnecessary leakage, and only the PSU protocols based on additively homomorphic encryption (AHE) can avoid the
leakage. However, the AHE-based PSU protocols are far from being practical.

To bridge the gap, we also design a new PSU protocol that can avoid the unnecessary leakage. Unlike the AHE-based PSU protocols, our new construction only relies on symmetric-key operations other than base OTs, thereby being much more scalable. The
experimental results demonstrate that our protocol can obtain at least 873.74× speedup over the best-performing AHE-based scheme. Moreover, our performance is comparable to that of the state-of-the-art PSU protocol (Chen et al., USENIX Security 2023),
which also suffers from the unnecessary leakage.



## 2024/923

* Title: On Orchestrating Parallel Broadcasts for Distributed Ledgers
* Authors: Peiyao Sheng, Chenyuan Wu, Dahlia Malkhi, Michael K. Reiter, Chrysoula Stathakopoulou, Michael Wei, Maofan Yin
* [Permalink](https://eprint.iacr.org/2024/923)
* [Download](https://eprint.iacr.org/2024/923.pdf)

### Abstract

This paper introduces and develops the concept of ``ticketing'', through which atomic broadcasts are orchestrated by nodes in a distributed system. The paper studies different ticketing regimes that allow parallelism, yet prevent slow nodes from
hampering overall progress. It introduces a hybrid scheme which combines managed and unmanaged ticketing regimes, striking a balance between adaptivity and resilience. The performance evaluation demonstrates how managed and unmanaged ticketing regimes
benefit throughput in systems with heterogeneous resources both in static and dynamic scenarios, with the managed ticketing regime performing better among the two as it adapts better. Finally, it demonstrates how using the hybrid ticketing regime
performance can enjoy both the adaptivity of the managed regime and the liveness guarantees of the unmanaged regime.



## 2024/924

* Title: Climbing and descending tall volcanos
* Authors: Steven Galbraith
* [Permalink](https://eprint.iacr.org/2024/924)
* [Download](https://eprint.iacr.org/2024/924.pdf)

### Abstract

We revisit the question of relating the elliptic curve discrete logarithm problem (ECDLP) between ordinary elliptic curves over finite fields with the same number of points. This problem was considered in 1999 by Galbraith and in 2005 by Jao, Miller, and
Venkatesan. We apply recent results from isogeny cryptography and cryptanalysis, especially the Kani construction, to this problem. We improve the worst case bound in Galbraith's 1999 paper from $\tilde{O}( q^{1.5} )$ to (heuristically) $\tilde{O}( q^{0.
4} )$ operations.

The two cases of main interest for discrete logarithm cryptography are random curves (flat volcanoes) and pairing-based crypto (tall volcanoes with crater of constant or polynomial size). In both cases we show a rigorous $\tO( q^{1/4})$ algorithm to
compute an isogeny between any two curves in the isogeny class. We stress that this paper is motivated by pre-quantum elliptic curve cryptography using ordinary elliptic curves, which is not yet obsolete.



## 2024/925

* Title: Time Sharing - A Novel Approach to Low-Latency Masking
* Authors: Dilip Kumar S. V., Siemen Dhooghe, Josep Balasch, Benedikt Gierlichs, Ingrid Verbauwhede
* [Permalink](https://eprint.iacr.org/2024/925)
* [Download](https://eprint.iacr.org/2024/925.pdf)

### Abstract

We present a novel approach to small area and low-latency first-order masking in hardware. The core idea is to separate the processing of shares in time in order to achieve non-completeness. Resulting circuits are proven first-order glitch-extended PINI
secure. This means the method can be straightforwardly applied to mask arbitrary functions without constraints which the designer must take care of. Furthermore we show that an implementation can benefit from optimization through EDA tools without
sacrificing security. We provide concrete results of several case studies. Our low-latency implementation of a complete PRINCE core shows a 32% area improvement (44% with optimization) over the state-of-the-art. Our PRINCE S-Box passes formal
verification with a tool and the complete core on FPGA shows no first-order leakage in TVLA with 100 million traces. Our low-latency implementation of the AES S-Box costs roughly one third (one quarter with optimization) of the area of state-of-the-art
implementations. It shows no first-order leakage in TVLA with 250 million traces.



## 2024/926

* Title: Verifiable and Private Vote-by-Mail
* Authors: Henri Devillez, Olivier Pereira, Thomas Peters
* [Permalink](https://eprint.iacr.org/2024/926)
* [Download](https://eprint.iacr.org/2024/926.pdf)

### Abstract

Vote-by-mail is increasingly used in Europe and worldwide for government elections. Nevertheless, very few attempts have been made towards the design of verifiable vote-by-mail, and none of them come with a rigorous security analysis. Furthermore, the
ballot privacy of the currently deployed (non-verifiable) vote-by-mail systems relies on procedural means that a single malicious operator can bypass.

We propose a verifiable vote-by-mail system that can accommodate the constraints of many of the large ballots that are common in Europe. Verifiability and privacy hold unless multiple system components collude to cheat on top of the postal channel. These
security notions are expressed and analyzed in the simplified UC security framework.

Our vote-by-mail system only makes limited requirements on the voters: voters can verify their vote by copying and comparing short strings and verifying the computation of a single hash on a short input, and they can vote normally if they want to ignore
the verification steps completely. Our system also relies on common cryptographic components, all available in the ElectionGuard verifiable voting SDK for instance, which limits the risks of errors in the implementation of the cryptographic aspects of
the system.



## 2024/927

* Title: MATHEMATICAL SPECULATIONS ON CRYPTOGRAPHY
* Authors: Anjali C B
* [Permalink](https://eprint.iacr.org/2024/927)
* [Download](https://eprint.iacr.org/2024/927.pdf)

### Abstract

The current cryptographic frameworks like RSA, ECC, and AES are potentially under quantum threat. Quantum cryptographic and post-quantum cryptography are being extensively researched for securing future information. The quantum computer and quantum
algorithms are still in the early developmental stage and thus lack scalability for practical application. As a result of these challenges, most researched PQC methods are lattice-based, code-based, ECC isogeny, hash-based, and multivariate crypto
schemes. In this paper, we explore other athematical topics such as stereographic projection, Mobius transformation, change of basis, Apollonian circle, Binary Quadratic form equivalence, Gauss composition law, and its conjunctions. It fulfills
preliminary conditions like bijection, primality, and np-hard problems, and the feasibility of one-way functions along with its interconnection. Thus allowing the exploration of new realms of mathematics for the development of secure protocols for future
communication.



## 2024/928

* Title: The Committing Security of MACs with Applications to Generic Composition
* Authors: Ritam Bhaumik, Bishwajit Chakraborty, Wonseok Choi, Avijit Dutta, Jérôme Govinden, Yaobin Shen
* [Permalink](https://eprint.iacr.org/2024/928)
* [Download](https://eprint.iacr.org/2024/928.pdf)

### Abstract

Message Authentication Codes (MACs) are ubiquitous primitives deployed in multiple flavors through standards such as HMAC, CMAC, GMAC, LightMAC, and many others. Its versatility makes it an essential building block in applications necessitating message
authentication and integrity checks, in authentication protocols, authenticated encryption schemes, or as a pseudorandom or key derivation function. Its usage in this variety of settings makes it susceptible to a broad range of attack scenarios. The
latest attack trends leverage a lack of commitment or context-discovery security in AEAD schemes and these attacks are mainly due to the weakness in the underlying MAC part. However, these new attack models have been scarcely analyzed for MACs themselves.
This paper provides a thorough treatment of MACs committing and context-discovery security. We reveal that commitment and context-discovery security of MACs have their own interest by highlighting real-world vulnerable scenarios. We formalize the
required security notions for MACs, and analyze the security of standardized MACs for these notions. Additionally, as a constructive application, we analyze generic AEAD composition and provide simple and efficient ways to build committing and context-
discovery secure AEADs.



## 2024/929

* Title: Combining Outputs of a Random Permutation: New Constructions and Tight Security Bounds by Fourier Analysis
* Authors: Itai Dinur
* [Permalink](https://eprint.iacr.org/2024/929)
* [Download](https://eprint.iacr.org/2024/929.pdf)

### Abstract

We consider constructions that combine outputs of a single permutation $\pi:\{0,1\}^n \rightarrow \{0,1\}^n$ using a public function. These are popular constructions for achieving security beyond the birthday bound when implementing a pseudorandom
function using a block cipher (i.e., a pseudorandom permutation). One of the best-known constructions (denoted SXoP$[2,n]$) XORs the outputs of 2 domain-separated calls to $\pi$.

Modeling $\pi$ as a uniformly chosen permutation, several previous works proved a tight information-theoretic indistinguishability bound for SXoP$[2,n]$ of about $q/2^{n}$, where $q$ is the number of queries. On the other hand, tight bounds are unknown
for the generalized variant (denoted SXoP$[r,n]$) which XORs the outputs of $r>2$ domain-separated calls to a uniform permutation.

In this paper, we obtain two results. Our first result improves the known bounds for SXoP$[r,n]$ for all (constant) $r \geq 3$ (assuming $q \leq O(2^n/r)$ is not too large) in both the single-user and multi-user settings. In particular, for $q=3$, our
bound is about $\sqrt{u}q_{\max}/2^{2.5n}$ (where $u$ is the number of users and $q_{\max}$ is the maximal number of queries per user), improving the best-known previous result by a factor of at least $2^n$.

For odd $r$, our bounds are tight for $q > 2^{n/2}$, as they match known attacks. For even $r$, we prove that our single-user bounds are tight by providing matching attacks.

Our second and main result is divided into two parts. First, we devise a family of constructions that output $n$ bits by efficiently combining outputs of 2 calls to a permutation on $\{0,1\}^n$, and achieve multi-user security of about $\sqrt{u} q_{\max}/
2^{1.5n}$. Then, inspired by the CENC construction of Iwata [FSE'06], we further extend this family to output $2n$ bits by efficiently combining outputs of 3 calls to a permutation on $\{0,1\}^n$. The extended construction has similar multi-user security
of $\sqrt{u} q_{\max}/2^{1.5n}$.

The new single-user ($u=1$) bounds of $q/2^{1.5n}$ for both families should be contrasted with the previously best-known bounds of $q/2^n$, obtained by the comparable constructions of SXoP$[2,n]$ and CENC.

All of our bounds are proved by Fourier analysis, extending the provable security toolkit in this domain in multiple ways.



## 2024/930

* Title: Information-Theoretic Single-Server PIR in the Shuffle Model
* Authors: Yuval Ishai, Mahimna Kelkar, Daniel Lee, Yiping Ma
* [Permalink](https://eprint.iacr.org/2024/930)
* [Download](https://eprint.iacr.org/2024/930.pdf)

### Abstract

We revisit the problem of private information retrieval (PIR) in the shuffle model, where queries can be made anonymously by multiple clients. We present the first single-server PIR protocol in this model that has sublinear per-client communication and
information-theoretic security. Moreover, following one-time preprocessing on the server side, our protocol only requires sublinear per-client computation. Concretely, for every $\gamma>0$, the protocol has $O(n^{\gamma})$ communication and computation
costs per (stateless) client, with $1/\text{poly}(n)$ statistical security, assuming that a size-$n$ database is simultaneously accessed by $\text{poly}(n)$ clients. This should be contrasted with the recent breakthrough result of Lin, Mook, and Wichs (
STOC 2023) on doubly efficient PIR in the standard model, which is (inherently) limited to computational security.



## 2024/931

* Title: Leveled Fully-Homomorphic Signatures from Batch Arguments
* Authors: Abtin Afshar, Jiaqi Cheng, Rishab Goyal
* [Permalink](https://eprint.iacr.org/2024/931)
* [Download](https://eprint.iacr.org/2024/931.pdf)

### Abstract

Fully homomorphic signatures are a significant strengthening of digital signatures, enabling computations on \emph{secretly} signed data. Today, we have multiple approaches to design fully homomorphic signatures such as from lattices, or succinct
functional commitments, or indistinguishability obfuscation, or mutable batch arguments. Unfortunately, all existing constructions for homomorphic signatures suffer from one or more limitations. We do not have homomorphic signatures with features such as
multi-hop evaluation, context hiding, and fast amortized verification, while relying on standard falsifiable assumptions.


In this work, we design homomorphic signatures satisfying all above properties. We construct homomorphic signatures for polynomial-sized circuits from a variety of standard assumptions such as sub-exponential DDH, standard pairing-based assumptions, or
learning with errors. We also discuss how our constructions can be easily extended to the multi-key setting.



## 2024/932

* Title: CISELeaks: Information Leakage Assessment of Cryptographic Instruction Set Extension Prototypes
* Authors: Aruna Jayasena, Richard Bachmann, Prabhat Mishra
* [Permalink](https://eprint.iacr.org/2024/932)
* [Download](https://eprint.iacr.org/2024/932.pdf)

### Abstract

Software based cryptographic implementations provide flexibility but they face performance limitations. In contrast, hardware based cryptographic accelerators utilize application-specific customization to provide real-time security solutions.
Cryptographic instruction-set extensions (CISE) combine the advantages of both hardware and software based solutions to provide higher performance combined with the flexibility of atomic-level cryptographic operations. While CISE is widely used to
develop security solutions, side-channel analysis of CISE-based devices is in its infancy. Specifically, it is important to evaluate whether the power usage and electromagnetic emissions of CISE-based devices have any correlation with its internal
operations, which an adversary can exploit to deduce cryptographic secrets.
In this paper, we propose a test vector leakage assessment framework to evaluate the pre-silicon prototypes at the early stages of the design life-cycle. Specifically, we first identify functional units with the potential for leaking information through
power side-channel signatures and then evaluate them on system prototypes by generating the necessary firmware to maximize the side-channel signature. Our experimental results on two RISC-V based cryptographic extensions, RISCV-CRYPTO and XCRYPTO,
demonstrated that seven out of eight prototype AES- and SHA-related functional units are vulnerable to leaking cryptographic secrets through their power side-channel signature even in full system mode with a statistical significance of $\alpha = 0.05$.



## 2024/933

* Title: A Pure Indistinguishability Obfuscation Approach to Adaptively-Sound SNARGs for NP
* Authors: Brent Waters, David J. Wu
* [Permalink](https://eprint.iacr.org/2024/933)
* [Download](https://eprint.iacr.org/2024/933.pdf)

### Abstract

We construct an adaptively-sound succinct non-interactive argument (SNARG) for NP in the CRS model from sub-exponentially-secure indistinguishability obfuscation ($i\mathcal{O}$) and sub-exponentially-secure one-way functions. Previously, Waters and Wu (
STOC 2024), and subsequently, Waters and Zhandry (CRYPTO 2024) showed how to construct adaptively-sound SNARGs for NP by relying on sub-exponentially-secure indistinguishability obfuscation, one-way functions, and an additional algebraic assumption (i.e.,
discrete log, factoring, or learning with errors). In this work, we show that no additional algebraic assumption is needed and vanilla (sub-exponentially-secure) one-way functions already suffice in combination with $i\mathcal{O}$.


[continued in next message]

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