[continued from previous message]

## 2023/1804

* Title: Fully Malicious Authenticated PIR
* Authors: Marian Dietz, Stefano Tessaro
* [Permalink](https://eprint.iacr.org/2023/1804)
* [Download](https://eprint.iacr.org/2023/1804.pdf)

### Abstract

Authenticated PIR enables a server to initially commit to a database of $N$ items, for which a client can later privately obtain individual items with complexity sublinear in $N$, with the added guarantee that the retrieved item is consistent with the
committed database. A crucial requirement is privacy with abort, i.e., the server should not learn anything about a query even if it learns whether the client aborts.

This problem was recently considered by Colombo et al. (USENIX '23), who proposed solutions secure under the assumption that the database is committed to honestly. Here, we close this gap, and present a solution that tolerates fully malicious servers
that provide potentially malformed commitments. Our scheme has communication and client computational complexity $\mathcal{O}_{\lambda}(\sqrt{N})$, solely relies on the DDH assumption, and does not introduce heavy machinery (e.g., generic succinct proofs)
. Privacy with abort holds provided the server succeeds in correctly answering $\lambda$ validation queries, which, from its perspective, are computationally indistinguishable from regular PIR queries. In fact, server side, our scheme is exactly the DDH-
based scheme by Colombo et al.



## 2023/1805

* Title: On the Security of Rate-limited Privacy Pass
* Authors: Hien Chu, Khue Do, Lucjan Hanzlik
* [Permalink](https://eprint.iacr.org/2023/1805)
* [Download](https://eprint.iacr.org/2023/1805.pdf)

### Abstract

The privacy pass protocol allows users to redeem anonymously issued cryptographic tokens instead of solving annoying CAPTCHAs. The issuing authority verifies the credibility of the user, who can later use the pass while browsing the web using an
anonymous or virtual private network. Hendrickson et al. proposed an IETF draft (privacypass-rate-limit-tokens-00) for a rate-limiting version of the privacy pass protocol, also called rate-limited Privacy Pass (RlP). Introducing a new actor called a
mediator makes both versions inherently different. The mediator applies access policies to rate-limit users’ access to the service while, at the same time, should be oblivious to the website/origin the user is trying to access. In this paper, we
formally define the rate-limited Privacy Pass protocol and propose a game-based security model to capture the informal security notions introduced by Hendrickson et al.. We show a construction from simple building blocks that fulfills our security
definitions and even allows for a post-quantum secure instantiation. Interestingly, the instantiation proposed in the IETF draft is a specific case of our construction. Thus, we can reuse the security arguments for the generic construction and show that
the version used in practice is secure.



## 2023/1806

* Title: Fast and Designated-verifier Friendly zkSNARKs in the BPK Model
* Authors: Xudong Zhu, Xuyang Song, Yi Deng
* [Permalink](https://eprint.iacr.org/2023/1806)
* [Download](https://eprint.iacr.org/2023/1806.pdf)

### Abstract

In ASIACRYPT 2016, Bellare et al. first demonstrated that it is impossible to achieve subversion soundness and standard zero knowledge simultaneously. Subsequently, there have been lots of effort to construct zero-knowledge succinct non interactive
arguments of knowledge protocols (zk-SNARKs) that satisfy subversion zero knowledge (S-ZK) and standard soundness from the zk-SNARK in the common reference string (CRS) model. The various constructions could be regarded secure in the bare public key (BPK)
model because of the equivalence between S-ZK in the CRS model, and uniform non-black-box zero knowledge in the BPK model has been proved by Abdolmaleki et al. in PKC 2020.

In this study, We proposed the first publicly verifiable non-uniform ZK zk-SNARK scheme in the BPK model maintaining comparable efficiency with its conventional counterpart, which can also be compatible with the well-known transformation proposed by
Bitansky et al. in TCC 2013 to obtain an efficient designated-verifier zk-SNARK. We achieve this goal by only adding a constant number of elements into the CRS, and using an unconventional but natural method to transform Groth’s zkSNARK in EUROCRYPT
2016. In addition, we propose a new speed-up technique that provides a trade-off. Specifically, if a logarithmic number of elements are added into the CRS, according to different circuits, the CRS verification time in our construction could be
approximately 9%-23% shorter than that in the conventional counterpart.



## 2023/1807

* Title: Entrada to Secure Graph Convolutional Networks
* Authors: Nishat Koti, Varsha Bhat Kukkala, Arpita Patra, Bhavish Raj Gopal
* [Permalink](https://eprint.iacr.org/2023/1807)
* [Download](https://eprint.iacr.org/2023/1807.pdf)

### Abstract

Graph convolutional networks (GCNs) are gaining popularity due to their powerful modelling capabilities. However, guaranteeing privacy is an issue when evaluating on inputs that contain users’ sensitive information such as financial transactions,
medical records, etc. To address such privacy concerns, we design Entrada, a framework for securely evaluating GCNs that relies on the technique of secure multiparty computation (MPC). For efficiency and accuracy reasons, Entrada builds over the MPC
framework of Tetrad (NDSS’22) and enhances the same by providing the necessary primitives. Moreover, Entrada leverages the GraphSC paradigm of Araki et al. (CCS’21) to further enhance efficiency. This entails designing a secure and efficient shuffle
protocol specifically in the 4-party setting, which to the best of our knowledge, is done for the first time and may be of independent interest. Through extensive experiments, we showcase that the accuracy of secure GCN evaluated via Entrada is on par
with its cleartext counterpart. We also benchmark efficiency of Entrada with respect to the included primitives as well as the framework as a whole. Finally, we showcase Entrada’s practicality by benchmarking GCN-based fraud detection application.



## 2023/1808

* Title: Small Stretch Problem of the DCT Scheme and How to Fix it
* Authors: Yuchao Chen, Tingting Guo, Lei Hu, Lina Shang, Shuping Mao, Peng Wang
* [Permalink](https://eprint.iacr.org/2023/1808)
* [Download](https://eprint.iacr.org/2023/1808.pdf)

### Abstract

DCT is a beyond-birthday-bound~(BBB) deterministic authenticated encryption~(DAE) mode proposed by Forler et al. in ACISP 2016, ensuring integrity by redundancy. The instantiation scheme of DCT employs the BRW polynomial, which is more efficient than the
usual polynomial function in GCM by reducing half of the multiplication operations. However, we show that DCT suffers from a small stretch problem similar to GCM. When the stretch length $\tau$ is small, choosing a special $m$-block message, we can
reduce the number of queries required by a successful forgery to $\mathcal{O}(2^{\tau}/m)$. We emphasize that this attack efficiently balances space and time complexity, but does not contradict the security bounds of DCT. Finally, we propose an improved
scheme named Robust DCT~(RDCT) with a minor change to DCT, which improves the security when $\tau$ is small and makes it resist the above attack.



## 2023/1809

* Title: PURED: A unified framework for resource-hard functions
* Authors: Alex Biryukov, Marius Lombard-Platet
* [Permalink](https://eprint.iacr.org/2023/1809)
* [Download](https://eprint.iacr.org/2023/1809.pdf)

### Abstract

Algorithm hardness can be described by 5 categories: hardness in computation, in sequential computation, in memory, in energy consumption (or bandwidth), in code size. Similarly, hardness can be a concern for solving or for verifying, depending on the
context, and can depend on a secret trapdoor or be universally hard. Two main lines of research investigated such problems: cryptographic puzzles, that gained popularity thanks to blockchain consensus systems (where solving must be moderately hard, and
verification either public or private), and white box cryptography (where solving must be hard without knowledge of the secret key). In this work, we improve upon the classification framework proposed by Biryukov and Perrin in Asiacypt 2017 and offer a
united hardness framework, PURED, that can be used for measuring all these kinds of hardness, both in solving and verifying. We also propose three new constructions that fill gaps previously uncovered by the literature (namely, trapdoor proof of CMC,
trapdoor proof of code, and a hard challenge in sequential time trapdoored in verification), and analyse their hardness in the PURED framework.



## 2023/1810

* Title: Pairing-Free Blind Signatures from Standard Assumptions in the ROM
* Authors: Julia Kastner, Ky Nguyen, Michael Reichle
* [Permalink](https://eprint.iacr.org/2023/1810)
* [Download](https://eprint.iacr.org/2023/1810.pdf)

### Abstract

Blind Signatures are a useful primitive for privacy preserving applications such as electronic payments, e-voting, anonymous credentials, and more. However, existing practical blind signature schemes based on standard assumptions require either pairings
or lattices. We present the first construction of a round-optimal blind signature in the random oracle model based on standard assumptions without resorting to pairings or lattices. In particular, our construction is secure under the strong RSA
assumption and DDH (in pairing-free groups). For our construction, we provide a NIZK-friendly signature based on strong RSA, and efficiently instantiate Fischlin's generic framework (CRYPTO'06). Our Blind Signature scheme has signatures of size 4.28 KB
and communication cost 62.19 KB. On the way, we develop techniques that might be of independent interest. In particular, we provide efficient relaxed range-proofs with subversion zero-knowledge and compact commitments to elements of arbitrary groups.



## 2023/1811

* Title: A note on Failing gracefully: Completing the picture for explicitly rejecting Fujisaki-Okamoto transforms using worst-case correctness
* Authors: Kathrin Hövelmanns, Christian Majenz
* [Permalink](https://eprint.iacr.org/2023/1811)
* [Download](https://eprint.iacr.org/2023/1811.pdf)

### Abstract

The Fujisaki-Okamoto (FO) transformation is used in most proposals for post-quantum secure key encapsulation mechanisms (KEMs) like, e.g., Kyber [BDK+18]. The security analysis of FO in the presence of quantum attackers has made huge progress over the
last years. Recently, [HHM22] made a particular improvement by giving a security proof that is agnostic towards how invalid ciphertexts are being treated: in contrast to previous proofs, it works regardless whether invalid ciphertexts are rejected by
reporting decryption failure explicitly or implicitly (by returning pseudorandom values).

The proof in [HHM22] involves a new correctness notion for the encryption scheme that is used to encapsulate the keys. This allows in principle for a smaller additive security related to decryption failures, but requires to analyze this new notion for
the encryption scheme on which a concrete KEM at hand is based.

This note offers a trade-off between [HHM22] and its predecessors: it offers a bound for both rejection variants, being mostly based on [HHM22], but uses a more established correctness notion.



## 2023/1812

* Title: The NTT and residues of a polynomial modulo factors of $X^{2^d} + 1$
* Authors: Sahil Sharma
* [Permalink](https://eprint.iacr.org/2023/1812)
* [Download](https://eprint.iacr.org/2023/1812.pdf)

### Abstract

The Number Theoretic Transform (NTT) plays a central role in efficient implementations of cryptographic primitives selected for Post Quantum Cryptography. Although it certainly exists, academic papers that cite the NTT omit the connection between the NTT
and residues of a polynomial modulo factors of $X^{2^d} + 1$ and mention only the final expressions of what the NTT computes. This short paper establishes that connection and, in doing so, elucidates key aspects of computing the NTT. Based on this, the
specific instantiations of the NTT function used in CRYSTALS-Kyber and CRYSTALS-Dilithium are derived.



## 2023/1813

* Title: Early Stopping for Any Number of Corruptions
* Authors: Julian Loss, Jesper Buus Nielsen
* [Permalink](https://eprint.iacr.org/2023/1813)
* [Download](https://eprint.iacr.org/2023/1813.pdf)

### Abstract

Minimizing the round complexity of byzantine broadcast is a fundamental question in distributed computing and cryptography. In this work, we present the first early stopping byzantine broadcast protocol that tolerates up to $t=n-1$ malicious corruptions
and terminates in $O(\min\{f^2,t+1\})$ rounds for any execution with $f\leq t$ actual corruptions. Our protocol is deterministic, adaptively secure, and works assuming a plain public key infrastructure. Prior early-stopping protocols all either require
honest majority or tolerate only up to $t=(1-\epsilon)n$ malicious corruptions while requiring either trusted setup or strong number theoretic hardness assumptions. As our key contribution, we show a novel tool called a polariser that allows us to
transfer certificate-based strategies from the honest majority setting to settings with a dishonest majority.



## 2023/1814

* Title: Easy-ABE: An Easy Ciphertext-Policy Attribute-Based Encryption
* Authors: Ahmad Khoureich Ka
* [Permalink](https://eprint.iacr.org/2023/1814)
* [Download](https://eprint.iacr.org/2023/1814.pdf)

### Abstract

Attribute-Based Encryption is widely recognized as a leap forward in the field of public key encryption. It allows to enforce an access control on encrypted data. Decryption time in ABE schemes can be long depending on the number of attributes and
pairing operations. This drawback hinders their adoption on a broader scale.

In this paper, we propose a non-monotone CP-ABE scheme that has no restrictions on the size of attribute sets and
policies, allows fast decryption and is adaptively secure under the CBDH-3 assumption. To achieve this, we approached the problem from a new angle, namely using a set membership relation for access structure. We have implemented our scheme using the Java
Pairing-Based Cryptography Library (JPBC) and the source code is available on GitHub.



## 2023/1815

* Title: Accelerating Polynomial Multiplication for RLWE using Pipelined FFT
* Authors: Neil Thanawala, Hamid Nejatollahi, Nikil Dutt
* [Permalink](https://eprint.iacr.org/2023/1815)
* [Download](https://eprint.iacr.org/2023/1815.pdf)

### Abstract

The evolution of quantum algorithms threatens to break public key cryptography in polynomial time. The development of quantum-resistant algorithms for the post-quantum era has seen a significant growth in the field of
post quantum cryptography (PQC). Polynomial multiplication is the core of
Ring Learning with Error (RLWE) lattice based cryptography (LBC) which
is one of the most promising PQC candidates. In this work, we present the design of fast and energy-efficient pipelined Number Theoretic Transform
(NTT) based polynomial multipliers and present synthesis results on a Field Programmable Gate Array (FPGA) to evaluate their efficacy.
NTT is performed using the pipelined R2SDF and R22SDF Fast Fourier
Transform (FFT) architectures. In addition, we propose an energy efficient modified architecture (Modr2). The NTT-based designed polynomial multipliers employs the Modr2 architecture that achieve on average 2× better
performance over the R2SDF FFT and 2.4× over the R22SDF FFT with
similar levels of energy consumption. The proposed polynomial multiplier
with Modr2 architecture reaches 12.5× energy efficiency over the state-ofthe-art convolution-based polynomial multiplier and 4× speedup over the
systolic array NTT based polynomial multiplier for polynomial degrees of
1024, demonstrating its potential for practical deployment in future designs.



## 2023/1816

* Title: ASOZ: a decentralized payment system with privacy preserving and auditing on public blockchain
* Authors: Tianjian Liu, Dawei Zhang, Wei Wang
* [Permalink](https://eprint.iacr.org/2023/1816)
* [Download](https://eprint.iacr.org/2023/1816.pdf)

### Abstract

Decentralized payment system gradually get more attention in recent years. By removing the trusted third party used for accounting ledgers, it fundamentally empowers users to control their own assets. As the privacy concerns grow, some cryptocurrencies
is proposed to preserve the privacy of users. However, those cryptocurrencies cause illegal transactions such as money laundering, fraudulent trading and so on. So it is necessary to design a auditing scheme. To solve this problem, many privacy-
preserving and audit scheme was proposed. But there exists no scheme that effectively solve the issue of privacy-preserving and auditing on both user identity and transaction content.
In this paper, we propose a design for a decentralized payment system with privacy preserving and auditing. We use cryptographic accumulators based on Merkle trees for accounting and use a combination of Twist ElGamal, NIZK (Non-Interactive Zero-
Knowledge), Bulletproofs, and zk-SNARKs for privacy preserving and auditing.



## 2023/1817

* Title: Authenticating Medications with QR-Codes and Compact Digital Signatures
* Authors: Julien Jainsky, David Naccache, Bassem Ouni, Ofer Yifrach-Stav
* [Permalink](https://eprint.iacr.org/2023/1817)
* [Download](https://eprint.iacr.org/2023/1817.pdf)

### Abstract

This paper describes a way to protect medications against falsification, a long-standing problem in the world.

We combine several existing technologies to achieve the stated goal. The building-blocks used are inherent physical randomness generated during the packaging process, artificial vision, short digital signatures and QR-codes.



## 2023/1818

* Title: On the Feasibility of Unleveled Fully-Homomorphic Signatures
* Authors: Romain Gay, Bogdan Ursu
* [Permalink](https://eprint.iacr.org/2023/1818)
* [Download](https://eprint.iacr.org/2023/1818.pdf)

### Abstract

We build the first unleveled fully homomorphic signature scheme in the standard model. Our scheme is not constrained by any a-priori bound on the depth of the functions that can be homomorphically evaluated, and relies on subexponentially-secure
indistinguishability obfuscation, fully-homomorphic encryption and a non-interactive zero-knowledge (NIZK) proof system with composable zero-knowledge. Our scheme is also the first to satisfy the strong security notion of context-hiding for an unbounded
number of levels, ensuring that signatures computed homomorphically do not leak the original messages from which they were computed. All building blocks are instantiable from falsifiable assumptions in the standard model, avoiding the need for knowledge
assumptions.
The main difficulty we overcome stems from the fact that bootstrapping, which is a crucial tool for obtaining unleveled fully homomorphic encryption (FHE), has no equivalent for homomorphic signatures, requiring us to use novel techniques.



## 2023/1819

* Title: Beyond MPC-in-the-Head: Black-Box Constructions of Short Zero-Knowledge Proofs
* Authors: Carmit Hazay, Muthuramakrishnan Venkitasubramaniam, Mor Weiss
* [Permalink](https://eprint.iacr.org/2023/1819)
* [Download](https://eprint.iacr.org/2023/1819.pdf)

### Abstract

In their seminal work, Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC`07) presented the MPC-in-the-Head paradigm, which shows how to design Zero-Knowledge Proofs (ZKPs) from secure Multi-Party Computation (MPC) protocols. This paradigm has since then
revolutionized and modularized the design of efficient ZKP systems, with far-reaching applications beyond ZKPs. However, to the best of our knowledge, all previous instantiations relied on fully-secure MPC protocols, and have not been able to leverage
the fact that the paradigm only imposes relatively weak privacy and correctness requirements on the underlying MPC.

In this work, we extend the MPC-in-the-Head paradigm to game-based cryptographic primitives supporting homomorphic computations (e.g., fully-homomorphic encryption, functional encryption, randomized encodings, homomorphic secret sharing, and more).
Specifically, we present a simple yet generic compiler from these primitives to ZKPs which use the underlying primitive as a black box. We also generalize our paradigm to capture commit-and-prove protocols, and use it to devise tight black-box compilers
from Interactive (Oracle) Proofs to ZKPs, assuming One-Way Functions (OWFs).

We use our paradigm to obtain several new ZKP constructions:

1. The first ZKPs for NP relations $\mathcal{R}$ computable in (polynomial-time uniform) $NC^1$, whose round complexity is bounded by a fixed constant (independent of the depth of $\mathcal{R}$'s verification circuit), with communication approaching
witness length (specifically, $n\cdot poly\left(\kappa\right)$, where $n$ is the witness length, and $\kappa$ is a security parameter), assuming DCR. Alternatively, if we allow the round complexity to scale with the depth of the verification circuit, our
ZKPs can make black-box use of OWFs.

2. Constant-round ZKPs for NP relations computable in bounded polynomial space, with $O\left(n\right)+o\left(m\right)\cdot poly\left(\kappa\right)$ communication assuming OWFs, where $m$ is the instance length. This gives a black-box alternative to a
recent non-black-box construction of Nassar and Rothblum (CRYPTO`22).

3. ZKPs for NP relations computable by a logspace-uniform family of depth-$d\left(m\right)$ circuits, with $n\cdot poly\left(\kappa,d\left(m\right)\right)$ communication assuming OWFs. This gives a black-box alternative to a result of Goldwasser, Kalai
and Rothblum (JACM).



## 2023/1820

* Title: Chipmunk: Better Synchronized Multi-Signatures from Lattices
* Authors: Nils Fleischhacker, Gottfried Herold, Mark Simkin, Zhenfei Zhang
* [Permalink](https://eprint.iacr.org/2023/1820)
* [Download](https://eprint.iacr.org/2023/1820.pdf)

### Abstract

Multi-signatures allow for compressing many signatures for the same message that were generated under independent keys into one small aggregated signature.
This primitive is particularly useful for proof-of-stake blockchains, like Ethereum, where the same block is signed by many signers, who vouch for the block's validity.
Being able to compress all signatures for the same block into a short string significantly reduces the on-chain storage costs, which is an important efficiency metric for blockchains.

In this work, we consider multi-signatures in the synchronized setting, where the signing algorithm takes an additional time parameter as input and it is only required that signatures for the same time step are aggregatable.
The synchronized setting is simpler than the general multi-signature setting, but is sufficient for most blockchain related applications, as signers are naturally synchronized by the length of the chain.

We present Chipmunk, a concretely efficient lattice-based multi-signature scheme in the synchronized setting that allows for signing an a-priori bounded number of messages.
Chipmunk allows for non-interactive aggregation of signatures and is secure against rogue-key attacks.
The construction is plausibly secure against quantum adversaries as our security relies on the assumed hardness of the short integer solution problem.

We significantly improve upon the previously best known construction in this setting by Fleischhacker, Simkin, and Zhang (CCS 2022).
Our aggregate signature size is $5.6 \times$ smaller and for $112$ bits of security our construction allows for compressing 8192 individual signatures into a multi-signature of size around $136$ KB.
We provide a full implementation of Chipmunk and provide extensive benchmarks studying our construction's efficiency.



## 2023/1821

* Title: Cryptanalysis of TS-Hash
* Authors: Aleksei Udovenko
* [Permalink](https://eprint.iacr.org/2023/1821)
* [Download](https://eprint.iacr.org/2023/1821.pdf)

### Abstract

This note presents attacks on the lightweight hash function TS-Hash proposed by Tsaban, including a polynomial-time preimage attack for short messages (at most n/2 bits), high-probability differentials, a general subexponential-time preimage attack, and
linearization techniques.

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