[continued from previous message]

This paper's purpose is to give a new method of analyzing Beale Cipher 1 and Cipher 3 and to show that there is no key which will decipher them into sentences.
Previous research has largely used statistical methods to
either decipher them or prove they have no solution. Some
of these methods show that there is a high probability, but not certainty that they are unsolvable. Both ciphers remain unsolved.
The methods used in this paper are not statistical ones
based on thousands of samples. The evidence given here shows there is a high correlation between locations of certain numbers in the ciphers with locations in the written text that was given with these ciphers in the 1885 pamphlet called "The Beale
Papers".
Evidence is correlated with a long monotonically increasing Gillogly String in Cipher 1, when translated with the Declaration of Independence given in the pamphlet.
The Beale Papers' writer was anonymous, and words in the three written letters in the 1885 pamphlet are compared with locations of numbers in the ciphers to show who the writer was.
Emphasis is on numbers which are controllable by the encipherer. Letter location sums are used when they are the most plausible ones found.
Evidence supports the statement that Cipher 1 and Cipher 3 are unintelligible. It also supports the statement that they were designed to have no intelligible sentences because they were part of a complex game made by the anonymous writer of The
Beale Papers.



## 2024/696

* Title: A Theoretical Take on a Practical Consensus Protocol
* Authors: Victor Shoup
* [Permalink](https://eprint.iacr.org/2024/696)
* [Download](https://eprint.iacr.org/2024/696.pdf)

### Abstract

The Asynchronous Common Subset (ACS) problem is a fundamental problem in distributed computing. Very recently, Das et al. (2024) developed a new ACS protocol with several desirable properties: (i) it provides optimal resilience, tolerating up to $t < n/
3$ corrupt parties out of $n$ parties in total, (ii) it does not rely on a trusted set up, (iii) it utilizes only "lighweight" cryptography, which can be instantiated using just a hash function, and (iv) it has expected round complexity $O(1)$ and
expected communication complexity $O(\kappa n^3)$, where $\kappa$ is the output-length of the hash function. The purpose of this paper is to give a detailed, self-contained exposition and analysis of this protocol from the point of view of modern
theoretcal cryptography, fleshing out a number of details of the definitions and proofs, providing a complete security analysis based on concrete security assumptions on the hash function (i.e., without relying on random oracles), and developing all of
the underlying theory in the universal composability framework.



## 2024/697

* Title: LINE: Cryptosystem based on linear equations for logarithmic signatures
* Authors: Gennady Khalimov, Yevgen Kotukh, Maksym Kolisnyk, Svitlana Khalimova, Oleksandr Sievierinov
* [Permalink](https://eprint.iacr.org/2024/697)
* [Download](https://eprint.iacr.org/2024/697.pdf)

### Abstract

The discourse herein pertains to a directional encryption cryptosystem predicated upon logarithmic signatures interconnected via a system of linear equations (we call it LINE). A logarithmic signature serves as a foundational cryptographic primitive
within the algorithm, characterized by distinct cryptographic attributes including nonlinearity, noncommutativity, unidirectionality, and factorizability by key. The confidentiality of the cryptosystem is contingent upon the presence of an incomplete
system of equations and the substantial ambiguity inherent in the matrix transformations integral to the algorithm. Classical cryptanalysis endeavors are constrained by the potency of the secret matrix transformation and the indeterminacy surrounding
solutions to the system of linear equations featuring logarithmic signatures. Such cryptanalysis methodologies, being exhaustive in nature, invariably exhibit exponential complexity. The absence of inherent group computations within the algorithm, and by
extension, the inability to exploit group properties associated with the periodicity of group elements, serves to mitigate quantum cryptanalysis to Grover's search algorithm. LINE is predicated upon an incomplete system of linear equations embodies the
security levels ranging from 1 to 5, as stipulated by the NIST, and thus presents a promising candidate for the construction of post-quantum cryptosystems.



## 2024/698

* Title: Private Computations on Streaming Data
* Authors: Vladimir Braverman, Kevin Garbe, Eli Jaffe, Rafail Ostrovsky
* [Permalink](https://eprint.iacr.org/2024/698)
* [Download](https://eprint.iacr.org/2024/698.pdf)

### Abstract

We present a framework for privacy-preserving streaming algorithms which combine the memory-efficiency of streaming algorithms with strong privacy guarantees. These algorithms enable some number of servers to compute aggregate statistics efficiently on
large quantities of user data without learning the user's inputs. While there exists limited prior work that fits within our model, our work is the first to formally define a general framework, interpret existing methods within this general framework,
and develop new tools broadly applicable to this model. To highlight our model, we designed and implemented a new privacy-preserving streaming algorithm to compute heavy hitters, which are the most frequent elements in a data stream. We provide a
performance comparison between our system and Poplar, the only other private statistics algorithm which supports heavy hitters. We benchmarked ours and Poplar's systems and provided direct performance comparisons within the same hardware platform. Of
note, Poplar requires linear space compared to our poly-logarithmic space, meaning our system is the first to compute heavy hitters within the privacy-preserving streaming model. A small memory footprint allows our algorithm (among other benefits) to run
efficiently on a very large input sizes without running out of memory or crashing.



## 2024/699

* Title: An Efficient All-to-All GCD Algorithm for Low Entropy RSA Key Factorization
* Authors: Elijah Pelofske
* [Permalink](https://eprint.iacr.org/2024/699)
* [Download](https://eprint.iacr.org/2024/699.pdf)

### Abstract

RSA is an incredibly successful and useful asymmetric encryption algorithm. One of the types of implementation flaws in RSA is low entropy of the key generation, specifically the prime number creation stage. This can occur due to flawed usage of random
prime number generator libraries, or on computers where there is a lack of a source of external entropy. These implementation flaws result in some RSA keys sharing prime factors, which means that the full factorization of the public modulus can be
recovered incredibly efficiently by performing a computation GCD between the two public key moduli that share the prime factor. However, since one does not know which of the composite moduli share a prime factor a-priori, to determine if any such shared
prime factors exist, an all-to-all GCD attack (also known as a batch GCD attack, or a bulk GCD attack) can be performed on the available public keys so as to recover any shared prime factors. This study describes a novel all-to-all batch GCD algorithm,
which will be referred to as the binary tree batch GCD algorithm, that is more efficient than the current best batch GCD algorithm (the remainder tree batch GCD algorithm). A comparison against the best existing batch GCD method (which is a product tree
followed by a remainder tree computation) is given using a dataset of random RSA moduli that are constructed such that some of the moduli share prime factors. This proposed binary tree batch GCD algorithm has better runtime than the existing remainder
tree batch GCD algorithm, although asymptotically it has nearly identical scaling and its complexity is dependent on how many shared prime factors exist in the set of RSA keys. In practice, the implementation of the proposed binary tree batch GCD
algorithm has a roughly 6x speedup compared to the standard remainder tree batch GCD approach.



## 2024/700

* Title: Sublinear Distributed Product Checks on Replicated Secret-Shared Data over $\mathbb{Z}_{2^k}$ without Ring Extensions
* Authors: Yun Li, Daniel Escudero, Yufei Duan, Zhicong Huang, Cheng Hong, Chao Zhang, Yifan Song
* [Permalink](https://eprint.iacr.org/2024/700)
* [Download](https://eprint.iacr.org/2024/700.pdf)

### Abstract

Multiple works have designed or used maliciously secure honest majority MPC protocols over $\mathbb{Z}_{2^k}$ using replicated secret sharing (e.g. Koti et al. USENIX’21, and the references therein). A recent trend in the design of such MPC protocols
is to first execute a semi-honest protocol, and then use a check that verifies the correctness of the computation requiring only sublinear amount of communication in terms of the circuit size. The so-called Galois ring extensions are needed in order to
execute such checks over $\mathbb{Z}_{2^k}$, but these rings incur incredibly high computation overheads, which completely undermine any potential benefits the ring $\mathbb{Z}_{2^k}$ had to begin with.
In this work we revisit the task of designing sublinear distributed product checks on replicated secret-shared data over $\mathbb{Z}_{2^k}$ among three parties with an honest majority. We present a novel technique for verifying the correctness of a set
of multiplication (in fact, inner product) triples, involving a sublinear cost in terms of the amount of multiplications. Most importantly, unlike previous works, our tools entirely avoid Galois ring extensions, and only require computation over rings of
the form $\mathbb{Z}_{2^l}$ . In terms of communication, our checks are 3∼5× lighter than existing checks using ring extensions, which is already quite remarkable. However, our most noticeable improvement is in terms of computation: avoiding
extensions allows our checks to be 17.7∼44.2× better than previous approaches, for many parameter regimes of interest. Our experimental results show that checking a 10 million gate circuit with the 3PC protocol from (Boyle et al., CCS’19) takes
about two minutes, while our approach takes only 2.82 seconds.
Finally, our techniques are not restricted to the three-party case, and we generalize them to replicated secret-sharing with an arbitrary number of parties n. Even though the share size in this scheme grows exponentially with n, prior works have used it
for n = 4 or n = 5—or even general n for feasibility results—and our distributed checks also represent improvements in these contexts.



## 2024/701

* Title: Quantum Unpredictability
* Authors: Tomoyuki Morimae, Shogo Yamada, Takashi Yamakawa
* [Permalink](https://eprint.iacr.org/2024/701)
* [Download](https://eprint.iacr.org/2024/701.pdf)

### Abstract

Unpredictable functions (UPFs) play essential roles in classical cryptography, including message authentication codes (MACs) and digital signatures. In this paper, we introduce a quantum analog of UPFs, which we call unpredictable state generators (UPSGs)
. UPSGs are implied by pseudorandom function-like states generators (PRFSs), which are a quantum analog of pseudorandom functions (PRFs), and therefore UPSGs could exist even if one-way functions do not exist, similar to other recently introduced
primitives like pseudorandom state generators (PRSGs), one-way state generators (OWSGs), and EFIs. In classical cryptography, UPFs are equivalent to PRFs, but in the quantum case, the equivalence is not clear, and UPSGs could be weaker than PRFSs.
Despite this, we demonstrate that all known applications of PRFSs are also achievable with UPSGs. They include IND-CPA-secure secret-key encryption and EUF-CMA-secure MACs with unclonable tags. Our findings suggest that, for many applications, quantum
unpredictability, rather than quantum pseudorandomness, is sufficient.



## 2024/702

* Title: Security Analysis of Signal's PQXDH Handshake
* Authors: Rune Fiedler, Felix Günther
* [Permalink](https://eprint.iacr.org/2024/702)
* [Download](https://eprint.iacr.org/2024/702.pdf)

### Abstract

Signal recently deployed a new handshake protocol named PQXDH to protect against "harvest-now-decrypt-later" attacks of a future quantum computer. To this end, PQXDH adds a post-quantum KEM to the Diffie-Hellman combinations of the prior X3DH handshake.

In this work, we give a reductionist security analysis of Signal's PQXDH handshake in a game-based security model that captures the targeted "maximum-exposure" security, allowing fine-grained compromise of user's long-term, semi-static, and ephemeral key
material. We augment prior such models to capture not only the added KEM component but also the signing of public keys, which prior analyses did not capture but which adds an additional flavor of post-quantum security in PQXDH. We then establish a fully
parameterized, concrete security bound for the session key security of PQXDH, in particular shedding light on a KEM binding property we require for PQXDH's security, and how to avoid it.

Our discussion of KEM binding complements the tool-based analysis of PQXDH by Bhargavan, Jacomme, Kiefer, and Schmidt, which pointed out a potential re-encapsulation attack if the KEM shared secret does not bind the public key. We show that both Kyber (
used in PQXDH) and its current NIST draft standard ML-KEM (foreseen to replace Kyber once standardized) satisfy a novel binding notion we introduce and rely on for our PQXDH analysis, which may be of independent interest.



## 2024/703

* Title: An Efficient and Extensible Zero-knowledge Proof Framework for Neural Networks
* Authors: Tao Lu, Haoyu Wang, Wenjie Qu, Zonghui Wang, Jinye He, Tianyang Tao, Wenzhi Chen, Jiaheng Zhang
* [Permalink](https://eprint.iacr.org/2024/703)
* [Download](https://eprint.iacr.org/2024/703.pdf)

### Abstract

In recent years, cloud vendors have started to supply paid services for data analysis by providing interfaces of their well-trained neural network models. However, customers lack tools to verify whether outcomes supplied by cloud vendors are correct
inferences from particular models, in the face of lazy or malicious vendors. The cryptographic primitive called zero-knowledge proof (ZKP) addresses this problem. It enables the outcomes to be verifiable without leaking information about the models.
Unfortunately, existing ZKP schemes for neural networks have high computational overheads, especially for the non-linear layers in neural networks.

In this paper, we propose an efficient and extensible ZKP framework for neural networks. Our work improves the performance of the proofs for non-linear layers. Compared to previous works relying on the technology of bit decomposition, we convert complex
non-linear relations into range and exponent relations, which significantly reduces the number of constraints required to prove non-linear layers. Moreover, we adopt a modular design to make our framework compatible with more neural networks.
Specifically, we propose two enhanced range and lookup proofs as basic blocks. They are efficient in proving the satisfaction of range and exponent relations. Then, we constrain the correct calculation of primitive non-linear operations using a small
number of range and exponent relations. Finally, we build our ZKP framework from the primitive operations to the entire neural networks, offering the flexibility for expansion to various neural networks.

We implement our ZKPs for convolutional and transformer neural networks. The evaluation results show that our work achieves over $168.6\times$ (up to $477.2\times$) speedup for separated non-linear layers and $41.4\times$ speedup for the entire ResNet-
101 convolutional neural network, when compared with the state-of-the-art work, Mystique. In addition, our work can prove GPT-2, a transformer neural network with $117$ million parameters, in $287.1$ seconds, achieving $35.7\times$ speedup over ZKML,
which is a state-of-the-art work supporting transformer neural networks.



## 2024/704

* Title: Fully Automated Selfish Mining Analysis in Efficient Proof Systems Blockchains
* Authors: Krishnendu Chatterjee, Amirali Ebrahim-Zadeh, Mehrdad Karrabi, Krzysztof Pietrzak, Michelle Yeo, Djordje Zikelic
* [Permalink](https://eprint.iacr.org/2024/704)
* [Download](https://eprint.iacr.org/2024/704.pdf)

### Abstract

We study selfish mining attacks in longest-chain blockchains like Bitcoin, but where the proof of work is replaced with efficient proof systems -- like proofs of stake or proofs of space -- and consider the problem of computing an optimal selfish mining
attack which maximizes expected relative revenue of the adversary, thus minimizing the chain quality. To this end, we propose a novel selfish mining attack that aims to maximize this objective and formally model the attack as a Markov decision process (
MDP). We then present a formal analysis procedure which computes an $\epsilon$-tight lower bound on the optimal expected relative revenue in the MDP and a strategy that achieves this $\epsilon$-tight lower bound, where $\epsilon>0$ may be any specified
precision. Our analysis is fully automated and provides formal guarantees on the correctness. We evaluate our selfish mining attack and observe that it achieves superior expected relative revenue compared to two considered baselines.

In concurrent work [Sarenche FC'24] does an automated analysis on selfish mining in predictable longest-chain blockchains based on efficient proof systems. Predictable means the randomness for the challenges is fixed for many blocks (as used e.g., in
Ouroboros), while
we consider unpredictable (Bitcoin-like) chains where the challenge is derived from the previous block.



## 2024/705

* Title: Large-Scale MPC: Scaling Private Iris Code Uniqueness Checks to Millions of Users
* Authors: Remco Bloemen, Daniel Kales, Philipp Sippl, Roman Walch
* [Permalink](https://eprint.iacr.org/2024/705)
* [Download](https://eprint.iacr.org/2024/705.pdf)

### Abstract

In this work we tackle privacy concerns in biometric verification systems that typically require server-side processing of sensitive data (e.g., fingerprints and Iris Codes). Concretely, we design a solution that allows us to query whether a given Iris
Code is similar to one contained in a given database, while all queries and datasets are being protected using secure multiparty computation (MPC). Addressing the substantial performance demands of operational systems like World ID and aid distributions
by the Red Cross, we propose new protocols to improve performance by more than three orders of magnitude compared to the recent state-of-the-art system Janus (S&P 24). Our final protocol can achieve a throughput of over a million Iris Code comparisons
per second on a single CPU core, while protecting the privacy of both the query and database Iris Codes. We additionally investigate GPU acceleration for some building blocks of our protocol, which results in further speedups of over 38x compared to the
respective multi-threaded CPU implementation.



## 2024/706

* Title: Linicrypt in the Ideal Cipher Model
* Authors: Zahra Javar, Bruce M. Kapron
* [Permalink](https://eprint.iacr.org/2024/706)
* [Download](https://eprint.iacr.org/2024/706.pdf)

### Abstract

We extend the Linicrypt framework for characterizing hash function security as proposed by McQuoid, Swope, and Rosulek (TCC 2018) to support constructions in the ideal cipher model.
In this setting, we give a characterization of collision- and second-preimage-resistance in terms of a linear-algebraic condition on Linicrypt programs, and present an efficient algorithm for determining whether a program satisfies the condition. As an
application, we consider the case of the block cipherbased hash functions proposed by Preneel, Govaerts, and Vandewall (Crypto 1993), and show that the semantic analysis of PGV given by Black et. al. (J. Crypto. 2010) can be captured as a special case of
our characterization. In addition, We model hash functions constructed through the Merkle-Damgård transformation within the Linicrypt framework. Finally, we appy this model to an analysis of how various attacks on the underlying compression functions
can compromise the collision resistance of the resulting hash function.



## 2024/707

* Title: Towards a Polynomial Instruction Based Compiler for Fully Homomorphic Encryption Accelerators
* Authors: Sejun Kim, Wen Wang, Duhyeong Kim, Adish Vartak, Michael Steiner, Rosario Cammarota
* [Permalink](https://eprint.iacr.org/2024/707)
* [Download](https://eprint.iacr.org/2024/707.pdf)

### Abstract

Fully Homomorphic Encryption (FHE) is a transformative technology that enables computations on encrypted data without requiring decryption, promising enhanced data privacy. However, its adoption has been limited due to significant performance overheads.
Recent advances include the proposal of domain-specific, highly-parallel hardware accelerators designed to overcome these limitations.
This paper introduces PICA, a comprehensive compiler framework designed to simplify the programming of these specialized FHE accelerators and integration with existing FHE libraries. PICA leverages a novel polynomial Instruction Set Architecture (p-ISA),
which abstracts polynomial rings and their arithmetic operations, serving as a fundamental data type for the creation of compact, efficient code embracing high-level operations on polynomial rings, referred to as kernels, e.g., encompassing FHE
primitives like arithmetic and ciphertext management. We detail a kernel generation framework that translates high-level FHE operations into pseudo-code using p-ISA, and a subsequent tracing framework that incorporates p-ISA functionalities and kernels
into established FHE libraries. Additionally, we introduce a mapper to coordinate multiple FHE kernels for optimal application performance on targeted hardware accelerators. Our evaluations demonstrate PICA's efficacy in creation of compact and efficient
code, when compared with an x64 architecture. Particularly in managing complex FHE operations such as relinearization, where we observe a 25.24x instruction count reduction even when a large batch size (8192) is taken into account.



## 2024/708

* Title: Automated Generation of Fault-Resistant Circuits
* Authors: Nicolai Müller, Amir Moradi
* [Permalink](https://eprint.iacr.org/2024/708)
* [Download](https://eprint.iacr.org/2024/708.pdf)

### Abstract

Fault Injection (FI) attacks, which involve intentionally introducing faults into a system to cause it to behave in an unintended manner, are widely recognized and pose a significant threat to the security of cryptographic primitives implemented in
hardware, making fault tolerance an increasingly critical concern. However, protecting cryptographic hardware primitives securely and efficiently, even with well-established and documented methods such as redundant computation, can be a time-consuming,
error-prone, and expertise-demanding task.
In this research, we present a comprehensive and fully-automated software solution for the Automated Generation of Fault-Resistant Circuits (AGEFA). Our application employs a generic and extensively researched methodology for the secure integration of
countermeasures based on Error-Correcting Codes (ECCs) into cryptographic hardware circuits. Our software tool allows designers without hardware security expertise to develop fault-tolerant hardware circuits with pre-defined correction capabilities under
a comprehensive fault adversary model. Moreover, our tool applies to masked designs without violating the masking security requirements, in particular to designs generated by the tool AGEMA. We evaluate the effectiveness of our approach through
experiments on various block ciphers and demonstrate its ability to produce fault-tolerant circuits. Additionally, we assess the security of examples generated by AGEFA against Side-Channel Analysis (SCA) and FI using state-of-the-art leakage and fault
evaluation tools.



## 2024/709

* Title: Masked Computation the Floor Function and its Application to the FALCON Signature
* Authors: Justine Paillet, Pierre-Augustin Berthet, Cédric Tavernier
* [Permalink](https://eprint.iacr.org/2024/709)
* [Download](https://eprint.iacr.org/2024/709.pdf)

### Abstract

FALCON is candidate for standardization of the new Post Quantum Cryptography (PQC) primitives by the National Institute of Standards and Technology (NIST). However, it remains a challenge to define efficient countermeasures against side-channel attacks (
SCA) for this algorithm. FALCON is a lattice-based signature that relies on rational numbers which is unusual in the cryptography field. While recent work proposed a solution to mask the addition and the multiplication, some roadblocks remain, most
noticeably how to protect the floor function. We propose in this work to complete the existing first trials of hardening FALCON against SCA. We perform the mathematical proofs of our methods as well as formal security proof in the probing model using the
Non-Interference concepts.



## 2024/710

* Title: BUFFing FALCON without Increasing the Signature Size
* Authors: Samed Düzlü, Rune Fiedler, Marc Fischlin
* [Permalink](https://eprint.iacr.org/2024/710)
* [Download](https://eprint.iacr.org/2024/710.pdf)

### Abstract

This work shows how FALCON can achieve the Beyond UnForgeability Features (BUFF) introduced by Cremers et al. (S&P'21) more efficiently than by applying the generic BUFF transform. Specifically, we show that applying a transform of Pornin and Stern (ACNS'
05), dubbed PS-3 transform, already suffices for FALCON to achieve BUFF security. For FALCON, this merely means to include the public key in the hashing step in signature generation and verification, instead of hashing only the nonce and the message; the
other signature computation steps and the signature output remain untouched. In comparison to the BUFF transform, which appends a hash value to the final signature, the PS-3 transform therefore achieves shorter signature sizes, without incurring
additional computations.



## 2024/711

* Title: Non-Transferable Anonymous Tokens by Secret Binding
* Authors: F. Betül Durak, Laurane Marco, Abdullah Talayhan, Serge Vaudenay
* [Permalink](https://eprint.iacr.org/2024/711)
* [Download](https://eprint.iacr.org/2024/711.pdf)

### Abstract

Non-transferability (NT) is a security notion which ensures that credentials are only used by their intended owners. Despite its importance, it has not been formally treated in the context of anonymous tokens (AT) which are lightweight anonymous
credentials. In this work, we consider a client who "buys" access tokens which are forbidden to be transferred although anonymously redeemed. We extensively study the trade-offs between privacy (obtained through anonymity) and security in AT through the
notion of non-transferability. We formalise new security notions, design a suite of protocols with various flavors of NT, prove their security, and implement the protocols to assess their efficiency. Finally, we study the existing anonymous credentials
which offer NT, and show that they cannot automatically be used as AT without security and complexity implications.



## 2024/712

* Title: Quantum NV Sieve on Grover for Solving Shortest Vector Problem
* Authors: Hyunji Kim, Kyungbae Jang, Hyunjun Kim, Anubhab Baksi, Sumanta Chakraborty, Hwajeong Seo
* [Permalink](https://eprint.iacr.org/2024/712)
* [Download](https://eprint.iacr.org/2024/712.pdf)

### Abstract

Quantum computers can efficiently model and solve several challenging problems for classical computers, raising concerns about potential security reductions in cryptography. NIST is already considering potential quantum attacks in the development of post-
quantum cryptography by estimating the quantum resources required for such quantum attacks. In this paper, we present quantum circuits for the NV sieve algorithm to solve the Shortest Vector Problem (SVP), which serves as the security foundation for
lattice-based cryptography, achieving a quantum speedup of the square root. Although there has been extensive research on the application of quantum algorithms for lattice-based problems at the theoretical level, specific quantum circuit implementations
for them have not been presented yet.

Notably, this work demonstrates that the required quantum complexity for the SVP in the lattice of rank 70 and dimension 70 is $2^{43}$ (a product of the total gate count and the total depth) with our optimized quantum implementation of the NV sieve
algorithm.

This complexity is significantly lower than the NIST post-quantum security standard, where level 1 is $2^{157}$, corresponding to the complexity of Grover's key search for AES-128.



## 2024/713

* Title: Analyzing Pump and jump BKZ algorithm using dynamical systems
* Authors: Leizhang Wang
* [Permalink](https://eprint.iacr.org/2024/713)
* [Download](https://eprint.iacr.org/2024/713.pdf)

### Abstract

The analysis of the reduction effort of the lattice reduction algorithm is important in estimating the hardness of lattice-based cryptography schemes. Recently many lattice challenge records have been cracked by using the Pnj-BKZ algorithm which is the
default lattice reduction algorithm used in G6K, such as the TU Darmstadt LWE and SVP Challenges. However, the previous estimations of the Pnj-BKZ algorithm are simulator algorithms rather than theoretical upper bound analyses. In this work, we present
the first dynamic analysis of Pnj-BKZ algorithm. More precisely, our analysis results show that let $L$ is the lattice spanned by $(\mathbf{a}_i)_{i\leq d}$. The shortest vector $\mathbf{b}_1$ output by running $\Omega \left ( \frac{2Jd^2}{\beta(\beta-J)}
\left ( \ln_{}{d} +\ln_{} \ln_{}{\max_{i}\frac{\left \| \mathbf{a}_i^{*} \right \| }{(\mathrm{det}L )^{1/d} } } \right ) \right ) $ tours reduction of pnj-BKZ$(\beta,J)$, $\mathbf{b}_1$ satisfied that \memo{$\left \| \mathbf{b}_1 \right \| \le {
\gamma}_{\beta}^{\frac{d-1}{2(\beta-J)}+2 } \cdot \left ( \mathrm{det}L \right ) ^{\frac{1}{d} } $}.



## 2024/714

* Title: Learning with Quantization, Polar Quantizer, and Secure Source Coding * Authors: Shanxiang Lyu, Ling Liu, Cong Ling
* [Permalink](https://eprint.iacr.org/2024/714)
* [Download](https://eprint.iacr.org/2024/714.pdf)

### Abstract

This paper presents a generalization of the Learning With Rounding (LWR) problem, initially introduced by Banerjee, Peikert, and Rosen, by applying the perspective of vector quantization. In LWR, noise is induced by rounding each coordinate to the
nearest multiple of a fraction, a process inherently tied to scalar quantization. By considering a new variant termed Learning With Quantization (LWQ), we explore large-dimensional fast-decodable lattices with superior quantization properties, aiming to
enhance the compression performance over conventional scalar quantization. We identify polar lattices as exemplary structures, effectively transforming LWQ into a problem akin to Learning With Errors (LWE), where the distribution of quantization noise is
statistically close to discrete Gaussian. Furthermore, we develop a novel ``quancryption'' scheme for secure source coding. Notably, the scheme achieves near-optimal rate-distortion ratios for bounded rational signal sources, and can be implemented
efficiently with quasi-linear time complexity. Python code of the polar-lattice quantizer is available at https://github.com/shx-lyu/PolarQuantizer.



## 2024/715

* Title: A New Cryptographic Algorithm
* Authors: Ali Mahdoum
* [Permalink](https://eprint.iacr.org/2024/715)

[continued in next message]

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