## In this issue

1. [2023/1387] Blockwise Rank Decoding Problem and LRPC Codes: ...
2. [2023/1925] VDOO: A Short, Fast, Post-Quantum Multivariate ...
3. [2023/1926] NOTRY: deniable messaging with retroactive avowal
4. [2023/1927] Holepunch: Fast, Secure File Deletion with Crash ...
5. [2023/1928] Unconditionally Secure Quantum Bit Commitment and ...
6. [2023/1929] Cryptography from Planted Graphs: Security with ...
7. [2023/1930] Toward A Practical Multi-party Private Set Union
8. [2023/1931] Single-Trace Side-Channel Attacks on CRYSTALS- ...
9. [2023/1932] Multipars: Reduced-Communication MPC over Z2k
10. [2023/1933] Keeping Up with the KEMs: Stronger Security Notions ...
11. [2023/1934] More efficient comparison protocols for MPC
12. [2023/1935] The Splitting Field of $Y^n-2$, Two-Variable NTT ...
13. [2023/1936] LERNA: Secure Single-Server Aggregation via Key- ...
14. [2023/1937] Revocable Quantum Digital Signatures
15. [2023/1938] Batch Arguments to NIZKs from One-Way Functions
16. [2023/1939] Applications of Neural Network-Based AI in Cryptography
17. [2023/1940] Concrete Time/Memory Trade-Offs in Generalised ...
18. [2023/1941] Upgrading Fuzzy Extractors
19. [2023/1942] Traceable mixnets
20. [2023/1943] Distinguisher and Related-Key Attack on HALFLOOP-96
21. [2023/1944] Revisiting The Multiple of Property for SKINNY The ...
22. [2023/1945] The Fiat--Shamir Transformation of ...
23. [2023/1946] SnarkFold: Efficient SNARK Proof Aggregation from ...
24. [2023/1947] Using Predicate Extension for Predicate Encryption ...
25. [2023/1948] PriDe CT: Towards Public Consensus, Private ...
26. [2023/1949] HELIOPOLIS: Verifiable Computation over ...
27. [2023/1950] GigaDORAM: Breaking the Billion Address Barrier

## 2023/1387

* Title: Blockwise Rank Decoding Problem and LRPC Codes: Cryptosystems with Smaller Sizes
* Authors: Yongcheng Song, Jiang Zhang, Xinyi Huang, Wei Wu
* [Permalink](https://eprint.iacr.org/2023/1387)
* [Download](https://eprint.iacr.org/2023/1387.pdf)

### Abstract

In this paper, we initiate the study of the Rank Decoding (RD) problem and LRPC codes with blockwise structures in rank-based cryptosystems. First, we introduce the blockwise errors ($\ell$-errors) where each error consists of $\ell$ blocks of
coordinates with disjoint supports, and define the blockwise RD ($\ell$-RD) problem as a natural generalization of the RD problem whose solutions are $\ell$-errors (note that the standard RD problem is actually a special $\ell$-RD problem with $\ell=1$).
We adapt the typical attacks on the RD problem to the $\ell$-RD problem, and find that the blockwise structures do not ease the problem too much: the $\ell$-RD problem is still exponentially hard for appropriate choices of $\ell>1$. Second, we introduce
blockwise LRPC ($\ell$-LRPC) codes as generalizations of the standard LPRC codes whose parity-check matrices can be divided into $\ell$ sub-matrices with disjoint supports, i.e., the intersection of two subspaces generated by the entries of any two sub-
matrices is a null space, and investigate the decoding algorithms for $\ell$-errors. We find that the gain of using $\ell$-errors in decoding capacity outweighs the complexity loss in solving the $\ell$-RD problem, which makes it possible to design more
efficient rank-based cryptosystems with flexible choices of parameters.

As an application, we show that the two rank-based cryptosystems submitted to the NIST PQC competition, namely, RQC and ROLLO, can be greatly improved by using the ideal variants of the $\ell$-RD problem and $\ell$-LRPC codes. Concretely, for 128-
bit security, our RQC has total public key and ciphertext sizes of 2.5 KB, which is not only about 50% more compact than the original RQC, but also smaller than the NIST Round 4 code-based submissions HQC, BIKE, and Classic McEliece.



## 2023/1925

* Title: VDOO: A Short, Fast, Post-Quantum Multivariate Digital Signature Scheme
* Authors: Anindya ganguly, Angshuman Karmakar, Nitin Saxena
* [Permalink](https://eprint.iacr.org/2023/1925)
* [Download](https://eprint.iacr.org/2023/1925.pdf)

### Abstract

Hard lattice problems are predominant in constructing post-quantum cryptosystems. However, we need to continue developing post-quantum cryptosystems based on other quantum hard problems to prevent a complete collapse of post-quantum cryptography due to a
sudden breakthrough in solving hard lattice problems. Solving large multivariate quadratic systems is one such quantum hard problem.

Unbalanced Oil-Vinegar is a signature scheme based on the hardness of solving multivariate equations. In this work, we present a post-quantum digital signature algorithm VDOO (Vinegar-Diagonal-Oil-Oil) based on solving multivariate equations. We
introduce a new layer called the diagonal layer over the oil-vinegar-based signature scheme Rainbow. This layer helps to improve the security of our scheme without increasing the parameters considerably. Due to this modification, the complexity of the
main computational bottleneck of multivariate quadratic systems i.e. the Gaussian elimination reduces significantly. Thus making our scheme one of the fastest multivariate quadratic signature schemes. Further, we show that our carefully chosen parameters
can resist all existing state-of-the-art attacks. The signature sizes of our scheme for the National Institute of Standards and Technology's security level of I, III, and V are 96, 226, and 316 bytes, respectively. This is the smallest signature size
among all known post-quantum signature schemes of similar security.



## 2023/1926

* Title: NOTRY: deniable messaging with retroactive avowal
* Authors: Faxing Wang, Shaanan Cohney, Riad Wahby, Joseph Bonneau
* [Permalink](https://eprint.iacr.org/2023/1926)
* [Download](https://eprint.iacr.org/2023/1926.pdf)

### Abstract

Modern secure messaging protocols typically aim to provide deniability. Achieving this requires that convincing cryptographic transcripts can be forged without the involvement of genuine users. In this work, we observe that parties may wish to revoke
deniability and avow a conversation after it has taken place. We propose a new protocol called Not-on-the-Record-Yet (NOTRY) which enables users to prove a prior conversation transcript is genuine. As a key building block we propose avowable designated
verifier proofs which may be of independent interest. Our implementation incurs roughly 8× communication and computation overhead over the standard Signal protocol during regular operation. We find it is nonetheless deployable in a realistic setting as
key exchanges (the source of the overhead) still complete in just over 1ms on a modern computer. The avowal protocol induces only constant computation and communication performance for the communicating parties and scales linearly in the number of
messages avowed for the verifier—in the tens of milliseconds per avowal.



## 2023/1927

* Title: Holepunch: Fast, Secure File Deletion with Crash Consistency
* Authors: Zachary Ratliff, Wittmann Goh, Abe Wieland, James Mickens, Ryan Williams
* [Permalink](https://eprint.iacr.org/2023/1927)
* [Download](https://eprint.iacr.org/2023/1927.pdf)

### Abstract

A file system provides secure deletion if, after a file is deleted, an attacker with physical possession of the storage device cannot recover any data from the deleted file. Unfortunately, secure deletion is not provided by commodity file systems. Even
file systems which explicitly desire to provide secure deletion are challenged by the subtleties of hardware controllers on modern storage devices; those controllers obscure the mappings between logical blocks and physical blocks, silently duplicate
physical blocks, and generally make it hard for host-level software to make reliable assumptions about how file data is kept on the device. State-of-the-art frameworks for secure deletion also have no crash consistency, meaning that an ill-timed power
outage or software fault will desynchonize keys and the associated encrypted file data, corrupting the file system.

In this paper, we present Holepunch, a new software-level approach for implementing secure deletion. Holepunch treats the storage device as a black box, providing secure deletion via cryptographic erasure. Holepunch uses per-file keys to transparently
encrypt outgoing file writes and decrypt incoming file reads, ensuring that all physical data in the storage device is always encrypted. Holepunch uses puncturable pseudorandom functions (PPRFs) to quickly access file keys; upon the deletion of file $f$,
Holepunch updates the PPRF so that, even if the PPRF is recovered, the PPRF cannot be used to generate $f$'s key. By using PPRFs instead of the key trees leveraged by prior work, Holepunch reduces both the memory pressure caused by key management and the
number of disk IOs needed to access files. Holepunch stores its master key in secure TPM storage, and uses a novel journaling scheme to provide crash consistency between TPM state and on-disk state.



## 2023/1928

* Title: Unconditionally Secure Quantum Bit Commitment and Quantum Oblivious Transfer
* Authors: Ping Wang, Yikang Lei, Yiting Su
* [Permalink](https://eprint.iacr.org/2023/1928)
* [Download](https://eprint.iacr.org/2023/1928.pdf)

### Abstract

Recently, a novel secure quantum bit commitment (QBC) protocol has been proposed [29]. However, the protocol requires Alice and Bob to share Bell states in advance, making the protocol lacking in practicality. In this paper, we propose two new
unconditionally secure quantum bit commitment protocols that do not require pre-shared Bell states based on entangled and non-entangled states, respectively. Their security stems from quantum mechanical properties such as quantum superposition, quantum
entanglement, no-cloning theorem, and no-communication theorem. Furthermore, by combining the proposed QBC with Yao's quantum oblivious transfer (QOT) model, we can obtain an unconditionally secure QOT protocol.



## 2023/1929

* Title: Cryptography from Planted Graphs: Security with Logarithmic-Size Messages
* Authors: Damiano Abram, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Varun Narayanan
* [Permalink](https://eprint.iacr.org/2023/1929)
* [Download](https://eprint.iacr.org/2023/1929.pdf)

### Abstract

We study the following broad question about cryptographic primitives: is it possible to achieve security against an arbitrary $\mathsf{poly}(n)$-time adversary with $O(\log n)$-size messages? It is common knowledge that the answer is ``no'' unless
information-theoretic security is possible. In this work, we revisit this question by considering the setting of cryptography with public information and computational security.

We obtain the following results, assuming variants of well-studied intractability assumptions:

1) A private simultaneous messages (PSM) protocol for every $f:[n]\times[n]\to\{0, 1\}$ requiring $(1+\epsilon)\log n$-bit messages for most functions and $(2+\epsilon)\log n$-bit messages for the remaining ones. We apply this towards non-interactive
secure 3-party computation with similar message size in the preprocessing model, improving over previous 2-round protocols.

2) A secret-sharing scheme for any ``forbidden-graph'' access structure on $n$ nodes with $O(\log n)$ share size.

3) On the negative side, we show that computational threshold secret-sharing schemes with public information require share size $\Omega(\log \log n)$. For arbitrary access structures, we show that computational security does not help with 1-bit shares.

The above positive results guarantee that any adversary of size $n^{o(\log n)}$ achieves an $n^{-\Omega(1)}$ distinguishing advantage. We show how to make the advantage negligible by slightly increasing the asymptotic message size, still improving over
all known constructions.
The security of our constructions is based on the conjectured hardness of variants of the planted clique problem, which was extensively studied in the algorithms, statistical inference, and complexity theory communities. Our work provides the first
applications of such assumptions improving the efficiency of mainstream cryptographic primitives, gives evidence for the necessity of such assumptions, and suggests new questions in this domain that may be of independent interest.



## 2023/1930

* Title: Toward A Practical Multi-party Private Set Union
* Authors: Jiahui Gao, Son Nguyen, Ni Trieu
* [Permalink](https://eprint.iacr.org/2023/1930)
* [Download](https://eprint.iacr.org/2023/1930.pdf)

### Abstract

This paper studies a multi-party private set union (mPSU), a fundamental cryptographic problem that allows multiple parties to compute the union of their respective datasets without revealing any additional information. We propose an efficient mPSU
protocol which is secure in the presence of any number of colluding semi-honest participants. Our protocol avoids computationally expensive homomorphic operations or generic multi-party computation, thus providing an efficient solution for mPSU.

The crux of our protocol lies in the utilization of new cryptographic tools, namely, Membership Oblivious Transfer (mOT) and Conditional Oblivious Pseudorandom Function (cOPRF). We believe that the mOT and cOPRF may be of independent interest.


We implement our mPSU protocol and evaluate their performance.
Our protocol shows an improvement of up to $55\times$ and $776.18\times$ bandwidth cost compared to the existing state-of-the-art protocols.



## 2023/1931

* Title: Single-Trace Side-Channel Attacks on CRYSTALS-Dilithium: Myth or Reality?
* Authors: Ruize Wang, Kalle Ngo, Joel Gärtner, Elena Dubrova
* [Permalink](https://eprint.iacr.org/2023/1931)
* [Download](https://eprint.iacr.org/2023/1931.pdf)

### Abstract

We present a side-channel attack on CRYSTALS-Dilithium, a post-quantum secure digital signature scheme, with two variants of post-processing. The side-channel attack exploits information leakage in the secret key unpacking procedure of the signing
algorithm to recover the coefficients of the polynomials in the secret key vectors ${\bf s}_1$ and ${\bf s}_2$ by profiled deep learning-assisted power analysis. In the first variant, one half of the coefficients of ${\bf s}_1$ and ${\bf s}_2$ is
recovered by power analysis and the rest is derived by solving a system of linear equations based on ${\bf t} = {\bf A}{\bf s}_1 + {\bf s}_2$, where ${\bf A}$ and ${\bf t}$ are parts of the public key. This case assumes knowledge of the least significant
bits of the vector ${\bf t}$, ${\bf t}_0$. The second variant waives this requirement. However, to succeed, it needs a larger portion of ${\bf s}_1$ to be recovered by power analysis. The remainder of ${\bf s}_1$ is obtained by lattice reduction. Once
the full ${\bf s}_1$ is recovered, all the other information necessary for generating valid signatures can be trivially derived from the public key. We evaluate both variants on an ARM Cortex-M4 implementation of Dilithium-2. The profiling stage (trace
capture and neural network training) takes less than 10 hours. In the attack assuming that ${\bf t}_0$ is known, the probability of successfully recovering the full vector ${\bf s}_1$ from a single trace captured from a different from profiling device is
non-negligible (9%). The success rate approaches 100% if multiple traces are available for the attack. Our results demonstrate the necessity of protecting the secret key of CRYSTALS-Dilithium from single-trace attacks and call for a reassessment of the
role of compression of the public key vector ${\bf t}$ in the security of CRYSTALS-Dilithium implementations.



## 2023/1932

* Title: Multipars: Reduced-Communication MPC over Z2k
* Authors: Sebastian Hasler, Pascal Reisert, Marc Rivinius, Ralf Küsters
* [Permalink](https://eprint.iacr.org/2023/1932)
* [Download](https://eprint.iacr.org/2023/1932.pdf)

### Abstract

In recent years, actively secure SPDZ-like protocols for dishonest majority, like SPD$\mathbb Z_{2^k}$, Overdrive2k, and MHz2k, over base rings $\mathbb Z_{2^k}$ have become more and more efficient. In this paper, we present a new actively secure MPC
protocol Multipars that outperforms these state-of-the-art protocols over $\mathbb Z_{2^k}$ by more than a factor of 2 in the two-party setup in terms of communication. Multipars is the first actively secure N-party protocol over $\mathbb Z_{2^k}$ that
is based on linear homomorphic encryption (LHE) in the offline phase (instead of oblivious transfer or somewhat homomorphic encryption in previous works). The strong performance of Multipars relies on a new adaptive packing for BGV ciphertexts that
allows us to reduce the parameter size of the encryption scheme and the overall communication cost. Additionally, we use modulus switching for further size reduction, a new type of enhanced CPA security over $\mathbb Z_{2^k}$, a truncation protocol for
Beaver triples, and a new LHE-based offline protocol without sacrificing over $\mathbb Z_{2^k}$.

We have implemented Multipars and therewith provide the fastest preprocessing phase over $\mathbb Z_{2^k}$. Our evaluation shows that Multipars offers at least a factor of 8 lower communication costs and up to a factor of 15 faster runtime in the WAN
setting compared to the currently best available actively secure MPC implementation over $\mathbb Z_{2^k}$.



## 2023/1933

* Title: Keeping Up with the KEMs: Stronger Security Notions for KEMs
* Authors: Cas Cremers, Alexander Dax, Niklas Medinger
* [Permalink](https://eprint.iacr.org/2023/1933)
* [Download](https://eprint.iacr.org/2023/1933.pdf)

### Abstract

Key Encapsulation Mechanisms (KEMs) are a critical building block for hybrid encryption and modern security protocols, notably in the post-quantum setting. Given the asymmetric public key of a recipient, the primitive establishes a shared secret key
between sender and recipient. In recent years, a large number of abstract designs and concrete implementations of KEMs have been proposed, notably in the context of the NIST selection process for post-quantum primitives.
The traditional security notion for KEMs has been the IND-CCA notion that was designed for public-key encryption (PKE). In recent work additional properties, such as robustness and anonymity, were lifted from the PKE setting to the KEMs setting.

In this work we introduce several stronger security notions for KEMs. Our new properties formalize in which sense outputs of the KEM uniquely determine, i.e., bind, other values.
Our new notions are based on two orthogonal observations: First, unlike PKEs, KEMs establish a unique key, which leads to natural binding properties for the established keys. Our new binding properties can be used, e.g., to prove the absence of attacks
that were not captured by prior security notions, such as re-encapsulation attacks. If we regard KEMs as one-pass key exchanges, our key-binding properties correspond to implicit key agreement properties.
Second, to prove the absence of weak keys, we have to consider not only honestly generated key pairs but also adversarially-generated key pairs.

We define a hierarchy of security notions for KEMs based on our observations. We position properties from the literature within our hierarchy, provide separating examples, and give examples of real world KEMs in the context of our hierarchy.



## 2023/1934

* Title: More efficient comparison protocols for MPC
* Authors: Wicher Malten, Mehmet Ugurbil, Miguel de Vega
* [Permalink](https://eprint.iacr.org/2023/1934)
* [Download](https://eprint.iacr.org/2023/1934.pdf)

### Abstract

In 1982, Yao introduced the problem of comparing two private values, thereby launching the study of protocols for secure multi-party computation (MPC). Since then, comparison protocols have undergone extensive study and found widespread applications.

We survey state-of-the-art comparison protocols for an arbitrary number of parties, decompose them into smaller primitives and analyse their communication complexity under the usual assumption that the underlying MPC protocol does preprocessing and
computes linear operations without communication. We then develop two new comparison protocols and explain why they are faster than similar protocols, including those that are commonly used in practice: they reduce the number of online multiplications,
without increasing preprocessing or round complexity. More concretely, online bandwidth is reduced by more than half for the standard comparison protocols whose round complexity is logarithmic in the bit-length, whereas for constant round comparison
protocols the reduction is two-thirds.



## 2023/1935

* Title: The Splitting Field of $Y^n-2$, Two-Variable NTT and Lattice-Based Cryptography
* Authors: Wenzhe Yang
* [Permalink](https://eprint.iacr.org/2023/1935)
* [Download](https://eprint.iacr.org/2023/1935.pdf)

### Abstract

The splitting field $F$ of the polynomial $Y^n-2$ is an extension over $\mathbb{Q}$ generated by $\zeta_n=\exp(2 \pi \sqrt{-1} /n)$ and $\sqrt[n]{2}$. When $n$ ($\geq 8$) is a power-of-two integer, the degree of $F$ over $\mathbb{Q}$ is $n^2/4$. In this
paper, we lay the foundation for applying the Order-LWE in $\mathcal{R}=\mathbb{Z}[\zeta_n, \sqrt[n]{2}]$ to cryptographic uses. More specifically, We will compute the Galois group $\text{Gal}\left(F/\mathbb{Q} \right)$ and the canonical embedding of $F$
into $\mathbb{C}^{n^2/4}$. Then we study the trace pairings of the integral basis $\zeta_n^{k_0} \sqrt[n]{2}^{k_1}$ and obtain its dual explicitly, which will be crucial when we study the error distributions on the ideal lattices associated with $\
mathcal{R}$.

Moreover, we design a Two-Variable Number Theoretic Transform (2NTT) algorithm for the quotient $\mathcal{R}_p=\mathcal{R}/p\mathcal{R}$, where $p$ is a prime number such that $Y^n \equiv 2 \bmod p$ has $n$ distinct solutions. Compared to the one-
variable NTT, a crucial advantage of 2NTT is that it enjoys a quadratic saving of twiddle factors. Hence, it is very interesting to see how to leverage this quadratic saving to boost the performance of 2NTT in practical implementations.



## 2023/1936

* Title: LERNA: Secure Single-Server Aggregation via Key-Homomorphic Masking
* Authors: Hanjun Li, Huijia Lin, Antigoni Polychroniadou, Stefano Tessaro
* [Permalink](https://eprint.iacr.org/2023/1936)
* [Download](https://eprint.iacr.org/2023/1936.pdf)

### Abstract

This paper introduces LERNA, a new framework for single-server secure aggregation. Our protocols are tailored to the setting where multiple consecutive aggregation phases are performed with the same set of clients, a fraction of which can drop out in
some of the phases. We rely on an initial secret sharing setup among the clients which is generated once-and-for-all, and reused in all following aggregation phases. Compared to prior works [Bonawitz et al. CCS’17, Bell et al. CCS’20], the reusable
setup eliminates one round of communication between the server and clients per aggregation—i.e., we need two rounds for semi-honest security (instead of three), and three rounds (instead of four) in the malicious model. Our approach also significantly
reduces the server’s computational costs by only requiring the reconstruction of a single secret-shared value (per aggregation). Prior work required reconstructing a secret-shared value for each client involved in the computation.

We provide instantiations of LERNA based on both the Decisional Composite Residuosity (DCR) and (Ring) Learning with Rounding ((R)LWR) assumptions respectively and evaluate a version based on the latter assumption. In addition to savings in round-
complexity (which result in reduced latency), our experiments show that the server computational costs are reduced by two orders of magnitude in comparison to the state-of-the-art. In settings with a large number of clients, we also reduce the
computational costs up to twenty-fold for most clients, while a small set of “heavy clients” is subject to a workload that is still smaller than that of prior work.



## 2023/1937

* Title: Revocable Quantum Digital Signatures
* Authors: Tomoyuki Morimae, Alexander Poremba, Takashi Yamakawa
* [Permalink](https://eprint.iacr.org/2023/1937)
* [Download](https://eprint.iacr.org/2023/1937.pdf)

### Abstract

We study digital signatures with revocation capabilities and show two results. First, we define and construct digital signatures with revocable signing keys from the LWE assumption. In this primitive, the signing key is a quantum state which enables a
user to sign many messages and yet, the quantum key is also revocable, i.e., it can be collapsed into a classical certificate which can later be verified. Once the key is successfully revoked, we require that the initial recipient of the key loses the
ability to sign. We construct digital signatures with revocable signing keys from a newly introduced primitive which we call two-tier one-shot signatures, which may be of independent interest. This is a variant of one-shot signatures, where the
verification of a signature for the message ``0'' is done publicly, whereas the verification for the message ``1'' is done in private. We give a construction of two-tier one-shot signatures from the LWE assumption. As a complementary result, we also
construct digital signatures with quantum revocation from group actions, where the quantum signing key is simply ``returned'' and then verified as part of revocation.

Second, we define and construct digital signatures with revocable signatures from OWFs. In this primitive, the signer can produce quantum signatures which can later be revoked. Here, the security property requires that, once revocation is successful, the
initial recipient of the signature loses the ability to find accepting inputs to the signature verification algorithm. We construct this primitive using a newly introduced two-tier variant of tokenized signatures. For the construction, we show a new
lemma which we call the adaptive hardcore bit property for OWFs, which may enable further applications.



## 2023/1938

* Title: Batch Arguments to NIZKs from One-Way Functions
* Authors: Eli Bradley, Brent Waters, David J. Wu
* [Permalink](https://eprint.iacr.org/2023/1938)
* [Download](https://eprint.iacr.org/2023/1938.pdf)

### Abstract

Succinctness and zero-knowledge are two fundamental properties in the study of cryptographic proof systems. Several recent works have formalized the connections between these two notions by showing how to realize non-interactive zero-knowledge (NIZK)
arguments from succinct non-interactive arguments. Specifically, Champion and Wu (CRYPTO 2023) as well as Bitansky, Kamath, Paneth, Rothblum, and Vasudevan (ePrint 2023) recently showed how to construct a NIZK argument for NP from a (somewhere-sound) non-
interactive batch argument (BARG) and a dual-mode commitment scheme (and in the case of the Champion-Wu construction, a local pseudorandom generator). The main open question is whether a BARG suffices for a NIZK (just assuming one-way functions).

In this work, we first show that an adaptively-sound BARG for NP together with an one-way function imply a computational NIZK argument for NP. We then show that the weaker notion of somewhere soundness achieved by existing BARGs from standard algebraic
assumptions are also adaptively sound if we assume sub-exponential security. This transformation may also be of independent interest. Taken together, we obtain a NIZK argument for NP from one-way functions and a sub-exponentially-secure somewhere-sound
BARG for NP.

If we instead assume plain public-key encryption, we show that a standard polynomially-secure somewhere-sound batch argument for NP suffices for the same implication. As a corollary, this means a somewhere-sound BARG can be used to generically upgrade
any semantically-secure public-key encryption scheme into one secure against chosen-ciphertext attacks. More broadly, our results demonstrate that constructing non-interactive batch arguments for NP is essentially no easier than constructing NIZK
arguments for NP.



## 2023/1939

* Title: Applications of Neural Network-Based AI in Cryptography
* Authors: Abderrahmane Nitaj, Tajjeeddine Rachidi
* [Permalink](https://eprint.iacr.org/2023/1939)
* [Download](https://eprint.iacr.org/2023/1939.pdf)

### Abstract

Artificial intelligence (AI) is a modern technology that allows plenty of advantages in daily life, such as predicting weather, finding directions, classifying images and videos, even automatically generating code, text, and videos. Other essential
technologies such as blockchain and cybersecurity also benefit from AI. As a core component used in blockchain and cybersecurity, cryptography can benefit from AI in order to enhance the confidentiality and integrity of cyberspace. In this paper, we
review the algorithms underlying four prominent cryptographic cryptosystems, namely the Advanced Encryption Standard, the Rivest--Shamir--Adleman, Learning With Errors, and the Ascon family of cryptographic algorithms for authenticated encryption. Where
possible, we pinpoint areas where AI can be used to help improve their security.



## 2023/1940

* Title: Concrete Time/Memory Trade-Offs in Generalised Stern’s ISD Algorithm * Authors: Sreyosi Bhattacharyya, Palash Sarkar
* [Permalink](https://eprint.iacr.org/2023/1940)
* [Download](https://eprint.iacr.org/2023/1940.pdf)

### Abstract

The first contribution of this work is a generalisation of Stern's information set decoding (ISD) algorithm. Stern's algorithm, a variant of Stern's algorithm due to Dumer, as well as a recent generalisation of Stern's algorithm due to Bernstein and Chou
are obtained as special cases of our generalisation. Our second contribution is to introduce the notion of a set of effective time/memory trade-off (TMTO) points for any ISD algorithm for given ranges of values of parameters of the algorithm. Such a set
succinctly and uniquely captures the entire landscape of TMTO points with only a minor loss in precision. We further describe a method to compute a set of effective TMTO points. As an application, we compute sets of effective TMTO points for the five
variants of the Classic McEliece cryptosystem corresponding to the new algorithm as well as for Stern's, Dumer's and Bernstein and Chou's algorithms. The results show that while Dumer's and Bernstein and Chou's algorithms do not provide any interesting
TMTO points beyond what is achieved by Stern's algorithm, the new generalisation that we propose provide about twice the number of effective TMTO points that is obtained from Stern's algorithm. Consequences of the obtained TMTO points to the
classification of the variants of Classic McEliece in appropriate NIST categories are discussed.



## 2023/1941

* Title: Upgrading Fuzzy Extractors
* Authors: Chloe Cachet, Ariel Hamlin, Maryam Rezapour, Benjamin Fuller
* [Permalink](https://eprint.iacr.org/2023/1941)
* [Download](https://eprint.iacr.org/2023/1941.pdf)

### Abstract

Fuzzy extractors derive stable keys from noisy sources non-interactively (Dodis et al., SIAM Journal of Computing 2008). Since their introduction, research has focused on two tasks: 1) showing security for as many distributions as possible and 2)
providing stronger security guarantees including allowing one to enroll the same value multiple times (reusability), security against an active attacker (robustness), and preventing leakage about the enrolled value (privacy).
Existing constructions of reusable fuzzy extractors are direct and do not support as many distributions as the best non-reusable constructions. Constructions of robust fuzzy extractors require strong assumptions even in the CRS model.

[continued in next message]

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