[digest] 2023 Week 28

[IACR ePrint Archive]

## In this issue

1. [2023/869] UniPlonk: Plonk with Universal Verifier
2. [2023/1053] ASMesh: Anonymous and Secure Messaging in Mesh ...
3. [2023/1054] Quantum Complexity for Discrete Logarithms and ...
4. [2023/1055] OccPoIs: Points of Interest based on Neural ...
5. [2023/1056] DIDO: Data Provenance from Restricted TLS 1.3 Websites
6. [2023/1057] ZK-for-Z2K: MPC-in-the-Head Zero-Knowledge Proofs ...
7. [2023/1058] Universal Amplification of KDM Security: From 1-Key ...
8. [2023/1059] Provably Secure Blockchain Protocols from ...
9. [2023/1060] Auditable Attribute-Based Credentials Scheme and ...
10. [2023/1061] BlindPerm: Efficient MEV Mitigation with an ...
11. [2023/1062] IOPs with Inverse Polynomial Soundness Error
12. [2023/1063] DiStefano: Decentralized Infrastructure for Sharing ...
13. [2023/1064] Decoding Quasi-Cyclic codes is NP-complete
14. [2023/1065] A Note on ``A Lightweight and Privacy-Preserving ...
15. [2023/1066] Efficient Arguments and Proofs for Batch Arithmetic ...
16. [2023/1067] How to Compile Polynomial IOP into Simulation- ...
17. [2023/1068] Optical Cryptanalysis: Recovering Cryptographic ...
18. [2023/1069] DuckyZip: Provably Honest Global Linking Service
19. [2023/1070] Fine-Grained Accountable Privacy via Unlinkable ...
20. [2023/1071] Fiat-Shamir Security of FRI and Related SNARKs
21. [2023/1072] Simple and Practical Single-Server Sublinear ...
22. [2023/1073] The Reality of Backdoored S-Boxes - An Eye Opener
23. [2023/1074] From MLWE to RLWE: A Differential Fault Attack on ...
24. [2023/1075] Streebog as a Random Oracle
25. [2023/1076] Threshold BBS+ From Pseudorandom Correlations
26. [2023/1077] Taming Adaptivity in YOSO Protocols: The Modular Way
27. [2023/1078] Bypassing Android isolation with fuel gauges: new ...
28. [2023/1079] Foundations of Data Availability Sampling
29. [2023/1080] ACORN-QRE: Specification and Analysis of a Method ...
30. [2023/1081] ARITHMETIZATION-ORIENTED APN FUNCTIONS
31. [2023/1082] Intmax2: A ZK-rollup with Minimal Onchain Data and ...
32. [2023/1083] Keyed Sum of Permutations: a simpler RP-based PRF
33. [2023/1084] A Side-Channel Attack on a Masked Hardware ...
34. [2023/1085] Fuzzy Deduplication Scheme Supporting Pre- ...
35. [2023/1086] On One-way Functions and the Worst-case Hardness of ...
36. [2023/1087] Moving a Step of ChaCha in Syncopated Rhythm
37. [2023/1088] Building Hard Problems by Combining Easy Ones
38. [2023/1089] Security-Performance Tradeoff in DAG-based Proof- ...
39. [2023/1090] Bulletproofs With Stochastic Equation Sets
40. [2023/1091] On Derandomizing Yao's Weak-to-Strong OWF Construction
41. [2023/1092] Adaptive attack for FESTA
42. [2023/1093] Lattice Isomorphism as a Group Action and Hard ...

## 2023/869

* Title: UniPlonk: Plonk with Universal Verifier
* Authors: Shumo Chu, Brandon H. Gomes, Francisco Hernandez Iglesias, Todd Norton, Duncan Tebbs
* [Permalink](https://eprint.iacr.org/2023/869)
* [Download](https://eprint.iacr.org/2023/869.pdf)

### Abstract

We propose UniPlonK, a modification of the PlonK protocol that uniformizes the Verifier’s work for families of circuits. Specifically, a single fixed-cost “Universal Verifier” can check proofs for circuits of different: sizes, public input lengths, selector polynomials, copy constraints, and even different custom gate sets. UniPlonK therefore extends the universality of PlonK beyond the SRS; it enables a single “Universal Verifier Circuit” capable of verifying proofs from different PlonK circuits.

The Universal Verifier’s marginal cost over the ordinary Plonk verifier is small: for circuits using only the vanilla Plonk gate, the Universal Verifier performs a number of additional field multiplications proportional to the logarithm of the maximum supported circuit size; it incurs no additional elliptic curve operations. For circuits using custom gates, the Universal Verifier incurs additional elliptic curve arithmetic only when verifying proofs from circuits that do not use all supported gate types. For circuits that use all supported gates, the Universal Verifier’s additional cost consists only of field multiplications proportional to the logarithm of the maximum supported circuit size, the number of custom gate types, and the number of witness variables used by these gates. In both settings (vanilla-only and custom gates) the marginal cost to the prover is a fixed-base MSM of size ℓ, the length of the public input vector.



## 2023/1053

* Title: ASMesh: Anonymous and Secure Messaging in Mesh Networks Using Stronger, Anonymous Double Ratchet
* Authors: Alexander Bienstock, Paul Rösler, Yi Tang
* [Permalink](https://eprint.iacr.org/2023/1053)
* [Download](https://eprint.iacr.org/2023/1053.pdf)

### Abstract

The majority of secure messengers have single, centralized service providers that relay ciphertexts between users to enable asynchronous communication. However, in some scenarios such as mass protests in censored networks, relying on a centralized provider is fatal. Mesh messengers attempt to solve this problem by building ad hoc networks in which user clients perform the ciphertext-relaying task. Yet, recent analyses of widely deployed mesh messengers discover severe security weaknesses (Albrecht et al. CT-RSA'21 & USENIX Security'22).

To support the design of secure mesh messengers, we provide a new, more complete security model for mesh messaging. Our model captures forward and post-compromise security, as well as forward and post-compromise anonymity, both of which are especially important in this setting. We also identify novel, stronger confidentiality goals that can be achieved due to the special characteristics of mesh networks (e.g., delayed communication, distributed network and adversary).

Finally, we develop a new protocol, called ASMesh, that provably satisfies these security goals. For this, we revisit Signal's Double Ratchet and propose non-trivial enhancements. On top of that, we add a mechanism that provides forward and post-compromise anonymity. Thus, our protocol efficiently provides strong confidentiality and anonymity under past and future user corruptions. Most of our results are also applicable to traditional messaging.

We prove security of our protocols and evaluate their performance in simulated mesh networks. Finally, we develop a proof of concept implementation.



## 2023/1054

* Title: Quantum Complexity for Discrete Logarithms and Related Problems
* Authors: Minki Hhan, Takashi Yamakawa, Aaram Yun
* [Permalink](https://eprint.iacr.org/2023/1054)
* [Download](https://eprint.iacr.org/2023/1054.pdf)

### Abstract

This paper studies the quantum computational complexity of the discrete logarithm and related group-theoretic problems in the context of ``generic algorithms''---that is, algorithms that do not exploit any properties of the group encoding.

We establish a generic model of quantum computation for group-theoretic problems, which we call the quantum generic group model, as a quantum analog of its classical counterpart. Shor's algorithm for the discrete logarithm problem and related algorithms can be described in this model. We show the quantum complexity lower bounds and (almost) matching algorithms of the discrete logarithm and related problems in this model. More precisely, we prove the following results for a cyclic group $\mathcal G$ of prime order.

(1) Any generic quantum discrete logarithm algorithm must make $\Omega(\log |\mathcal G|)$ depth of group operation queries. This shows that Shor's algorithm that makes $O(\log |\mathcal G|)$ group operations is asymptotically optimal among the generic quantum algorithms, even considering parallel algorithms.
(2) We observe that some (known) variations of Shor's algorithm can take advantage of classical computations to reduce the number and depth of quantum group operations. We introduce a model for generic hybrid quantum-classical algorithm that captures these variants, and show that these algorithms are almost optimal in this model. Any generic hybrid quantum-classical algorithm for the discrete logarithm problem with a total number of (classical or quantum) group operations $Q$ must make $\Omega(\log |\mathcal G|/\log Q)$ quantum group operations of depth $\Omega(\log\log |\mathcal G| - \log\log Q)$. In particular, if $Q={\rm poly}\log |\mathcal G|$, classical group operations can only save the number of quantum queries by a factor of $O(\log\log |\mathcal G|)$ and the quantum depth remains as $\Omega(\log\log |\mathcal G|)$.
(3) When the quantum memory can only store $t$ group elements and use quantum random access memory (qRAM) of $r$ group elements, any generic hybrid quantum-classical algorithm must make either $\Omega(\sqrt{|\mathcal G|})$ group operation queries in total or $\Omega(\log |\mathcal G|/\log (tr))$ quantum group operation queries. In particular, classical queries cannot reduce the number of quantum queries beyond $\Omega(\log |\mathcal G|/\log (tr))$.

As a side contribution, we show a multiple discrete logarithm problem admits a better algorithm than solving each instance one by one, refuting a strong form of the quantum annoying property suggested in the context of password-authenticated key exchange protocol.



## 2023/1055

* Title: OccPoIs: Points of Interest based on Neural Network's Key Recovery in Side-Channel Analysis through Occlusion
* Authors: Trevor Yap, Shivam Bhasin, Stjepan Picek
* [Permalink](https://eprint.iacr.org/2023/1055)
* [Download](https://eprint.iacr.org/2023/1055.pdf)

### Abstract

Deep neural networks (DNNs) represent a powerful technique for assessing cryptographic security concerning side-channel analysis (SCA) due to their ability to aggregate leakages automatically, rendering attacks more efficient without preprocessing. Nevertheless, despite their effectiveness, DNNs employed in SCA are predominantly black-box algorithms, posing considerable interpretability challenges.
In this paper, we propose a novel technique called Key Guessing Occlusion (KGO) that acquires a minimal set of sample points required by the DNN for key recovery, which we call OccPoIs. These OccPoIs provide information on which areas of the traces are important to the DNN for retrieving the key, enabling evaluators to know where to refine their cryptographic implementation.
After obtaining the OccPoIs, we first explore the leakages found in these OccPoIs to understand what the DNN is learning with first-order Correlation Power Analysis (CPA). We show that KGO obtains relevant sample points that have a high correlation with the given leakage model but also acquires sample points that first-order CPA fails to capture. Furthermore, unlike the first-order CPA in the masking setting, KGO obtains these OccPoIs without the knowledge of the shares or mask.
Next, we employ the template attack (TA) using the OccPoIs to investigate if KGO could be used as a feature selection tool.
We show that using the OccPoIs with TA can recover the key for all the considered synchronized datasets and is consistent as a feature selection tool even on datasets protected by first-order masking.
Furthermore, it also allows a more efficient attack than other feature selections on the first-order masking dataset called ASCADf.



## 2023/1056

* Title: DIDO: Data Provenance from Restricted TLS 1.3 Websites
* Authors: Kwan Yin Chan, Handong Cui, Tsz Hon Yuen
* [Permalink](https://eprint.iacr.org/2023/1056)
* [Download](https://eprint.iacr.org/2023/1056.pdf)

### Abstract

Public data can be authenticated by obtaining from a trustworthy website with TLS. Private data, such as user profile, are usually restricted from public access. If a user wants to authenticate his private data (e.g., address) provided by a restricted website (e.g., user profile page of a utility company website) to a verifier, he cannot simply give his username and password to the verifier. DECO (CCS 2020) provides a solution for liberating these data without introducing undesirable trust assumption, nor requiring server-side modification. Their implementation is mainly based on TLS 1.2.

In this paper, we propose an optimized solution for TLS 1.3 websites. We tackle a number of open problems, including the support of X25519 key exchange in TLS 1.3, the design of round-optimal three-party key exchange, the architecture of two-party computation of TLS 1.3 key scheduling, and circuit design optimized for two-party computation. We test our implementation with real world website and show that our optimization is necessary to avoid timeout in TLS handshake.



## 2023/1057

* Title: ZK-for-Z2K: MPC-in-the-Head Zero-Knowledge Proofs for $\mathbb{Z}_{2^k}$
* Authors: Lennart Braun, Cyprien Delpech de Saint Guilhem, Robin Jadoul, Emmanuela Orsini, Nigel P. Smart, Titouan Tanguy
* [Permalink](https://eprint.iacr.org/2023/1057)
* [Download](https://eprint.iacr.org/2023/1057.pdf)

### Abstract

In this work, we extend the MPC-in-the-head framework, used in recent efficient zero-knowledge protocols, to work over the ring $\mathbb{Z}_{2^k}$, which is the primary operating domain for modern CPUs. The proposed schemes are compatible with any threshold linear secret sharing scheme and draw inspiration from MPC protocols adapted for ring operations. Additionally, we explore various batching methodologies, leveraging Shamir's secret sharing schemes and Galois ring extensions, and show the applicability of our approach in RAM program verification. Finally, we analyse different options for instantiating the resulting ZK scheme over rings and compare their communication costs.



## 2023/1058

* Title: Universal Amplification of KDM Security: From 1-Key Circular to Multi-Key KDM
* Authors: Brent Waters, Daniel Wichs
* [Permalink](https://eprint.iacr.org/2023/1058)
* [Download](https://eprint.iacr.org/2023/1058.pdf)

### Abstract

An encryption scheme is Key Dependent Message (KDM) secure if it is safe to encrypt messages that can arbitrarily depend on the secret keys themselves. In this work, we show how to upgrade essentially the weakest form of KDM security into the strongest one. In particular, we assume the existence of a symmetric-key bit-encryption that is circular-secure in the $1$-key setting, meaning that it maintains security even if one can encrypt individual bits of a single secret key under itself. We also rely on a standard CPA-secure public-key encryption. We construct a public-key encryption scheme that is KDM secure for general functions (of a-priori bounded circuit size) in the multi-key setting, meaning that it maintains security even if one can encrypt arbitrary functions of arbitrarily many secret keys under each of the public keys. As a special case, the latter guarantees security in the presence of arbitrary length key cycles. Prior work already showed how to amplify $n$-key circular to $n$-key KDM security for general functions. Therefore, the main novelty of our work is to upgrade from $1$-key to $n$-key security for arbitrary $n$.

As an independently interesting feature of our result, our construction does not need to know the actual specification of the underlying 1-key circular secure scheme, and we only rely on the existence of some such scheme in the proof of security. In particular, we present a universal construction of a multi-key KDM-secure encryption that is secure as long as some 1-key circular-secure scheme exists. While this feature is similar in spirit to Levin's universal construction of one-way functions, the way we achieve it is quite different technically, and does not come with the same ``galactic inefficiency''.



## 2023/1059

* Title: Provably Secure Blockchain Protocols from Distributed Proof-of-Deep-Learning
* Authors: Xiangyu Su, Mario Larangeira, Keisuke Tanaka
* [Permalink](https://eprint.iacr.org/2023/1059)
* [Download](https://eprint.iacr.org/2023/1059.pdf)

### Abstract

Proof-of-useful-work (PoUW), an alternative to the widely used proof-of-work (PoW), aims to re-purpose the network's computing power. Namely, users evaluate meaningful computational problems, e.g., solving optimization problems, instead of computing numerous hash function values as in PoW. A recent approach utilizes the training process of deep learning as ``useful work''. However, these works lack security analysis when deploying them with blockchain-based protocols, let alone the informal and over-complicated system design. This work proposes a distributed proof-of-deep-learning (D-PoDL) scheme concerning PoUW's requirements. With a novel hash-traininßg-hash structure and model-referencing mechanism, our scheme is the first deep learning-based PoUW scheme that enables achieving better accuracy distributively. Next, we introduce a transformation from the D-PoDL scheme to a generic D-PoDL blockchain protocol which can be instantiated with two chain selection rules, i.e., the longest-chain rule and the weight-based blockchain framework (LatinCrypt' 21). This work is the first to provide formal proofs for deep learning-involved blockchain protocols concerning the robust ledger properties, i.e., chain growth, chain quality, and common prefix. Finally, we implement the D-PoDL scheme to discuss the effectiveness of our design.



## 2023/1060

* Title: Auditable Attribute-Based Credentials Scheme and Its Applications in Contact Tracing
* Authors: Pengfei Wang, Xiangyu Su, Mario Larangeira, Keisuke Tanaka
* [Permalink](https://eprint.iacr.org/2023/1060)
* [Download](https://eprint.iacr.org/2023/1060.pdf)

### Abstract

During the pandemic, the limited functionality of existing privacy-preserving contact tracing systems highlights the need for new designs. Wang et al. proposed an environmental-adaptive framework (CSS '21) but failed to formalize the security. The similarity between their framework and attribute-based credentials (ABC) inspires us to reconsider contact tracing from the perspective of ABC schemes. In such schemes, users can obtain credentials on attributes from issuers and prove the credentials anonymously (i.e., hiding sensitive information of both user and issuer). This work first extends ABC schemes with auditability, which enables designated auditing authorities to revoke the anonymity of particular issuers. We show a concrete construction by adding a DDH-based ``auditable public key'' mechanism to the Connolly et al.'s ABC scheme (PKC '22). In this work we present three contributions regarding the auditable ABC: (1) we refine the environmental-adaptive contact tracing framework, (2) present a formal treatment which includes game-based security definition and a detailed protocol construction. Finally, (3) we implement our construction to showcase the practicality of our protocol.



## 2023/1061

* Title: BlindPerm: Efficient MEV Mitigation with an Encrypted Mempool and Permutation
* Authors: Alireza Kavousi, Duc V. Le, Philipp Jovanovic, George Danezis
* [Permalink](https://eprint.iacr.org/2023/1061)
* [Download](https://eprint.iacr.org/2023/1061.pdf)

### Abstract

Maximal extractable value (MEV) in the context of blockchains and cryptocurrencies refers to the highest potential profit that an actor, particularly a miner or validator, can achieve through their ability to include, exclude, or re-order transactions within the blocks. MEV has become a topic of concern within the Web3 community as it impacts the fairness and security of the cryptocurrency ecosystem. In this work, we propose and explore techniques that utilize randomized permutations to shuffle the order of transactions of a committed block before they are executed.
We also show that existing MEV mitigation approaches using an encrypted mempool can be readily extended by permutation-based techniques, thus providing multi-layer protection. With a focus on BFT consensus, we then propose BlindPerm, a framework enhancing an encrypted mempool with permutation at essentially no additional overheads and present various optimizations. Finally, we demonstrate how to extend our mitigation technique to support PoW longest-chain consensus protocols.



## 2023/1062

* Title: IOPs with Inverse Polynomial Soundness Error
* Authors: Gal Arnon, Alessandro Chiesa, Eylon Yogev
* [Permalink](https://eprint.iacr.org/2023/1062)
* [Download](https://eprint.iacr.org/2023/1062.pdf)

### Abstract

We show that every language in NP has an Interactive Oracle Proof (IOP) with inverse polynomial soundness error and small query complexity. This achieves parameters that surpass all previously known PCPs and IOPs. Specifically, we construct an IOP with perfect completeness, soundness error $1/n$, round complexity $O(\log \log n)$, proof length $poly(n)$ over an alphabet of size $O(n)$, and query complexity $O(\log \log n)$. This is a step forward in the quest to establish the sliding-scale conjecture for IOPs (which would additionally require query complexity $O(1)$).

Our main technical contribution is a high-soundness small-query proximity test for the Reed-Solomon code. We construct an IOP of proximity for Reed-Solomon codes, over a field $\mathbb{F}$ with evaluation domain $L$ and degree $d$, with perfect completeness, soundness error (roughly) $\max\{1-\delta , O(\rho^{1/4})\}$ for $\delta$-far functions, round complexity $O(\log \log d)$, proof length $O(|L|/\rho)$ over $\mathbb{F}$, and query complexity $O(\log \log d)$; here $\rho = (d+1)/|L|$ is the code rate. En route, we obtain a new high-soundness proximity test for bivariate Reed-Muller codes.

The IOP for NP is then obtained via a high-soundness reduction from NP to Reed-Solomon proximity testing with rate $\rho = 1/poly(n)$ and distance $\delta = 1-1/poly(n)$ (and applying our proximity test). Our constructions are direct and efficient, and hold the potential for practical realizations that would improve the state-of-the-art in real-world applications of IOPs.



## 2023/1063

* Title: DiStefano: Decentralized Infrastructure for Sharing Trusted Encrypted Facts and Nothing More
* Authors: Sofía Celi, Alex Davidson, Hamed Haddadi, Gonçalo Pestana, Joe Rowell
* [Permalink](https://eprint.iacr.org/2023/1063)
* [Download](https://eprint.iacr.org/2023/1063.pdf)

### Abstract

We design DiStefano: an efficient framework for generating private commitments over TLS-encrypted web traffic for a designated, untrusted third-party. DiStefano provides many improvements over previous TLS commitment systems, including: a modular security model that is applicable to TLS 1.3 traffic, and support for generating verifiable claims using applicable zero-knowledge systems; inherent 1-out-of-n privacy for the TLS server that the client communicates with; and various cryptographic optimisations to ensure fast online performance of the TLS session. We build an open-source implementation of DiStefano integrated into the BoringSSL cryptographic library, that is used within Chromium-based Internet browsers. We show that DiStefano is practical for committing to facts in arbitrary TLS traffic, with online times that are comparable with existing TLS 1.2 solutions. We also make improvements to certain cryptographic primitives used inside DiStefano, leading to 3x and 2x improvements in online computation time and bandwidth in specific situations.



## 2023/1064

* Title: Decoding Quasi-Cyclic codes is NP-complete
* Authors: Ernesto Dominguez Fiallo, Pablo Freyre Arrozarena, Luis Ramiro Piñeiro
* [Permalink](https://eprint.iacr.org/2023/1064)
* [Download](https://eprint.iacr.org/2023/1064.pdf)

### Abstract

We prove that the problem of decoding a Quasi-Cyclic (QC) code is NP-hard, and the corresponding decision problem is NP-complete. Our proof is based on a new characterization of quasi-cyclic codes closely related to linear random codes. We also discuss the cryptographic significance of this result.



## 2023/1065

* Title: A Note on ``A Lightweight and Privacy-Preserving Mutual Authentication and Key Agreement Protocol for Internet of Drones Environment''
* Authors: Zhengjun Cao, Lihua Liu
* [Permalink](https://eprint.iacr.org/2023/1065)
* [Download](https://eprint.iacr.org/2023/1065.pdf)

### Abstract

We show that the key agreement scheme [IEEE Internet Things J., 9(12), 2022, 9918--9933] is flawed. In order to authenticate each other, all participants use message authentication code (MAC) to generate tags for exchanged data. But MAC is a cryptographic technique which requires that the sender and receiver share a symmetric key. The scheme tries to establish a new shared key by using an old shared key, which results in a vicious circle. To the best of our knowledge, it is the first time to discuss such a flaw in the related literatures.



## 2023/1066

* Title: Efficient Arguments and Proofs for Batch Arithmetic Circuit Satisfiability
* Authors: Jieyi Long
* [Permalink](https://eprint.iacr.org/2023/1066)
* [Download](https://eprint.iacr.org/2023/1066.pdf)

### Abstract

In this paper, we provide a systematic treatment for the batch arithmetic circuit satisfiability and evaluation problem. Building on the core idea which treats circuit inputs/outputs as a low-degree polynomials, we explore various interactive argument and proof schemes that can produce succinct proofs with short verification time. In particular, for the batch satisfiability problem, we provide a construction of succinct interactive argument of knowledge for generic log-space uniform circuits based on the bilinear pairing and common reference string assumption. Our argument has size in $O(poly(\lambda) \cdot (|\mathbf{w}| + d \log |C|))$, where $\lambda$ is the security parameter, $|\mathbf{w}|$ is the size of the witness, and $d$ and $|C|$ are the depth and size of the circuit, respectively. Note that the argument size is independent of the batch size. To the best of our knowledge, asymptotically it is the smallest among all known batch argument schemes that allow public verification. The batch satisfiablity problem simplifies to a batch evaluation problem when the circuit only takes in public inputs (i.e., no witness). For the evaluation problem, we construct statistically sound interactive proofs for various special yet highly important types of circuits, including linear circuits, and circuits representing sum of polynomials. Our proposed protocols are able to achieve proof sizes independent of the batch size. We also describe protocols optimized specifically for batch FFT and batch matrix multiplication which achieve desirable properties, including lower prover time and better composability. We believe these protocols are of interest in their own right and can be used as primitives in more complex applications.



## 2023/1067

* Title: How to Compile Polynomial IOP into Simulation-Extractable SNARKs: A Modular Approach
* Authors: Markulf Kohlweiss, Mahak Pancholi, Akira Takahashi
* [Permalink](https://eprint.iacr.org/2023/1067)
* [Download](https://eprint.iacr.org/2023/1067.pdf)

### Abstract

Most succinct arguments (SNARKs) are initially only proven knowledge sound (KS).
We show that the commonly employed compilation strategy from polynomial interactive oracle proofs (PIOP) via polynomial commitments to knowledge sound SNARKS actually also achieves other desirable properties: weak unique response (WUR) and trapdoorless zero-knowledge (TLZK); and that together they imply simulation extractability (SIM-EXT).

The factoring of SIM-EXT into KS + WUR + TLZK is becoming a cornerstone of the analysis of non-malleable SNARK systems. We show how to prove WUR and TLZK for PIOP compiled SNARKs under mild falsifiable assumptions on the polynomial commitment scheme. This means that the analysis of knowledge soundness from PIOP properties that inherently relies on non-falsifiable or idealized assumption such as the algebraic group model (AGM) or generic group model (GGM) need not be repeated.

While the proof of WUR requires only mild assumptions on the PIOP, TLZK is a different matter. As perfectly hiding polynomial commitments sometimes come at a substantial performance premium, SNARK designers prefer to employ deterministic commitments with some leakage. This results in the need for a stronger zero-knowledge property for the PIOP.

The modularity of our approach implies that any analysis improvements, e.g. in terms of tightness, credibility of the knowledge assumption and model of the KS analysis, or the precision of capturing real-world optimizations for TLZK also benefits the SIM-EXT guarantees.



## 2023/1068

* Title: Optical Cryptanalysis: Recovering Cryptographic Keys from Power LED Light Fluctuations
* Authors: Ben Nassi, Ofek Vayner, Etay Iluz, Dudi Nassi, Or Hai Cohen, Jan Jancar, Daniel Genkin, Eran Tromer, Boris Zadov, Yuval Elovici
* [Permalink](https://eprint.iacr.org/2023/1068)
* [Download](https://eprint.iacr.org/2023/1068.pdf)

### Abstract

Although power LEDs have been integrated in various
devices that perform cryptographic operations for decades, the
cryptanalysis risk they pose has not yet been investigated.
In this paper, we present optical cryptanalysis, a new form
of cryptanalytic side-channel attack, in which secret keys are
extracted by using a photodiode to measure the light emitted
by a device’s power LED and analyzing subtle fluctuations in
the light intensity during cryptographic operations. We analyze
the optical leakage of power LEDs of various consumer
devices and the factors that affect the optical SNR. We then
demonstrate end-to-end optical cryptanalytic attacks against
a range of consumer devices (smartphone, smartcard, and
Raspberry Pi, along with their USB peripherals) and recover
secret keys (RSA, ECDSA, SIKE) from prior and recent
versions of popular cryptographic libraries (GnuPG, Libgcrypt,
PQCrypto-SIDH) from a maximum distance of 25 meters



## 2023/1069

* Title: DuckyZip: Provably Honest Global Linking Service
* Authors: Nadim Kobeissi
* [Permalink](https://eprint.iacr.org/2023/1069)
* [Download](https://eprint.iacr.org/2023/1069.pdf)

### Abstract

DuckyZip is a provably honest global linking service which links short memorable identifiers to arbitrarily large payloads (URLs, text, documents, archives, etc.) without being able to undetectably provide different payloads for the same short identifier to different parties. DuckyZip uses a combination of Verifiable Random Function (VRF)-based zero knowledge proofs and a smart contract in order to provide strong security guarantees: despite the transparency of the smart contract log, observers cannot feasibly create a mapping of all short identifiers to payloads that is faster than $\mathcal{O}(n)$ classical enumeration.



## 2023/1070

* Title: Fine-Grained Accountable Privacy via Unlinkable Policy-Compliant Signatures
* Authors: Christian Badertscher, Mahdi Sedaghat, Hendrik Waldner
* [Permalink](https://eprint.iacr.org/2023/1070)
* [Download](https://eprint.iacr.org/2023/1070.pdf)

### Abstract

Privacy-preserving payment systems face the difficult task of balancing privacy and accountability: on one hand, users should be able to transact privately and anonymously, on the other hand, no illegal activities should be tolerated. The challenging question of finding the right balance lies at the core of the research on accountable privacy that stipulates the use of cryptographic techniques for policy enforcement, but still allows an authority to revoke the anonymity of transactions whenever such an automatic enforcement is technically not supported. Current state-of-the-art systems are only able to enforce rather limited policies, such as spending or transaction limits, or assertions about participants, but are unable to enforce more complex policies that for example jointly evaluate both, the private credentials of sender and recipient-let alone to do this without an auditor in the loop during payment. This limits the cases where privacy revocation can be avoided as the method to fulfill regulations, which is unsatisfactory from a data-protection viewpoint and shows the need for cryptographic solutions that are able to elevate accountable privacy to a more fine-grained level.

In this work, we present such a solution. We show how to enforce complex policies while offering strong privacy and anonymity guarantees by enhancing the notion of policy-compliant signatures (PCS) introduced by Badertscher, Matt and Waldner (TCC'21). In more detail, we first define the notion of unlinkable PCS (ul-PCS) and show how this cryptographic primitive can be generically integrated with a wide range of systems including UTxO-based ledgers, privacy-preserving protocols like Monero or Zcash, and central-bank digital currencies. We give a generic construction for ul-PCS for any policy, and optimized constructions tailored for special policy classes, such as role-based policies and separable policies.

To bridge the gap between theory and practice, we provide prototype implementations for all our schemes. We give the first benchmarks for policy-compliant signatures in general, and demonstrate their feasibility for reasonably sized attribute sets for the special cases.



## 2023/1071

* Title: Fiat-Shamir Security of FRI and Related SNARKs
* Authors: Alexander R. Block, Albert Garreta, Jonathan Katz, Justin Thaler, Pratyush Ranjan Tiwari, Michał Zając
* [Permalink](https://eprint.iacr.org/2023/1071)
* [Download](https://eprint.iacr.org/2023/1071.pdf)

### Abstract

We establish new results on the Fiat-Shamir (FS) security of several protocols that are widely used in practice, and we provide general tools for establishing similar results for others. More precisely, we: (1) prove the FS security of the FRI and batched FRI protocols; (2) analyze a general class of protocols, which we call $\delta$-correlated, that use low-degree proximity testing as a subroutine (this includes many "Plonk-like" protocols (e.g., Plonky2 and Redshift), ethSTARK, RISC Zero, etc.); and (3) prove FS security of the aforementioned "Plonk-like" protocols, and sketch how to prove the same for the others.

We obtain our first result by analyzing the round-by-round (RBR) soundness and RBR knowledge soundness of FRI. For the second result, we prove that if a $\delta$-correlated protocol is RBR (knowledge) sound under the assumption that adversaries always send low-degree polynomials, then it is RBR (knowledge) sound in general. Equipped with this tool, we prove our third result by formally showing that "Plonk-like" protocols are RBR (knowledge) sound under the assumption that adversaries always send low-degree polynomials. We then outline analogous arguments for the remainder of the aforementioned protocols.

To the best of our knowledge, ours is the first formal analysis of the Fiat-Shamir security of FRI and widely deployed protocols that invoke it.



## 2023/1072

* Title: Simple and Practical Single-Server Sublinear Private Information Retrieval
* Authors: Muhammad Haris Mughees, Ling Ren
* [Permalink](https://eprint.iacr.org/2023/1072)
* [Download](https://eprint.iacr.org/2023/1072.pdf)

### Abstract

We present a simple and lightweight single-server sublinear private information retrieval scheme based on new techniques in hint construction and usage. Our scheme has small amortized response and close to optimal online response, which is only twice that of simply fetching the desired entry without privacy. For a 128 GB database with 64-byte entries, each query consumes only 117 KB of communication and 7.5 milliseconds of computation, amortized.



## 2023/1073

* Title: The Reality of Backdoored S-Boxes - An Eye Opener
* Authors: Shah Fahd, Mehreen Afzal, Waseem Iqbal, Dawood Shah, Ijaz Khalid
* [Permalink](https://eprint.iacr.org/2023/1073)
* [Download](https://eprint.iacr.org/2023/1073.pdf)

### Abstract

The analysis of real-life incidents has revealed that state-level efforts are made to camouflage the intentional flaws in the mathematical layer of an S-Box to exploit the information-theoretic properties, i.e., Kuznyechik. To extract and investigate the common features in the backdoored S-Box(es), this research thoroughly examines them from the perspective of 24 cryptanalytic attack vectors available in the open literature. We have debunked the earlier claims by the backdoor engineers that their designs are stealthy against statistical distinguishers. A backdoored architecture fulfils the notions of randomness but lacks the strength to resist sophisticated cryptanalytic attacks. Our analysis has revealed that during the backdoor insertion phase, a malicious designer compromises vital cryptographic properties, prominently the algebraic degree, differential trails, avalanche characteristics and leaving the open ground for hybrid attacks. It is observed that these mappings attain the upper bound of BCT, FBCT and DLCT, thus paving the way for hybrid attacks with high probability.



## 2023/1074

* Title: From MLWE to RLWE: A Differential Fault Attack on Randomized & Deterministic Dilithium
* Authors: Mohamed ElGhamrawy, Melissa Azouaoui, Olivier Bronchain, Joost Renes, Tobias Schneider, Markus Schönauer, Okan Seker, Christine van Vredendaal
* [Permalink](https://eprint.iacr.org/2023/1074)
* [Download](https://eprint.iacr.org/2023/1074.pdf)

### Abstract

The post-quantum digital signature scheme CRYSTALS-Dilithium has
been recently selected by the NIST for standardization. Implementing CRYSTALS-Dilithium, and other post-quantum cryptography schemes, on embedded devices raises a new set of challenges, including ones related to performance in terms of speed and memory requirements, but also related to side-channel and fault injection attacks security. In this work, we investigated the latter and describe a differential fault attack on the randomized and deterministic versions of CRYSTALS-Dilithium. Notably, the attack requires a few instructions skips and is able to reduce the MLWE problem that Dilithium is based on to a smaller RLWE problem which can be practically solved with lattice reduction techniques. Accordingly, we demonstrated key recoveries using hints extracted on the secret keys from the same faulted signatures using the LWE with side-information framework introduced by Dachman-Soled et al. at CRYPTO’20. As a final contribution, we proposed algorithmic countermeasures against this attack and in particular showed that the second one can be parameterized to only induce a negligible overhead over the signature generation.



## 2023/1075

* Title: Streebog as a Random Oracle
* Authors: Liliya Akhmetzyanova, Alexandra Babueva, Andrey Bozhko
* [Permalink](https://eprint.iacr.org/2023/1075)
* [Download](https://eprint.iacr.org/2023/1075.pdf)

### Abstract

The random oracle model is an instrument used for proving that protocol has no structural flaws when settling with standard hash properties is impossible or fairly difficult. In practice, however, random oracles have to be instantiated with some specific hash functions, which are not random oracles. Hence, in the real world, an adversary has broader capabilities than considered in the random oracle proof — it can exploit the peculiarities of a specific hash function to achieve its goal. In a case when a hash function is based on some building block, one can go further and show that even if the adversary has access to that building block, the hash function still behaves like a random oracle under some assumptions made about the building block. Thereby, the protocol can be proved secure against more powerful adversaries under less complex assumptions. The indifferentiability notion formalizes that approach.

In this paper we study whether Streebog, a Russian standardized hash function, can instantiate a random oracle from that point of view. We prove that Streebog is indifferentiable from a random oracle under an ideal cipher assumption for the underlying block cipher.



## 2023/1076

* Title: Threshold BBS+ From Pseudorandom Correlations
* Authors: Sebastian Faust, Carmit Hazay, David Kretzler, Benjamin Schlosser
* [Permalink](https://eprint.iacr.org/2023/1076)
* [Download](https://eprint.iacr.org/2023/1076.pdf)

### Abstract

The BBS+ signature scheme is one of the most prominent solutions for realizing anonymous credentials. In particular, due to properties like selective disclosure and efficient protocols for creating and showing possession of credentials. In recent years, research in cryptography has increasingly focused on the distribution of cryptographic tasks to mitigate attack surfaces and remove single points of failure.

In this work, we present a threshold BBS+ protocol in the preprocessing model. Our protocol supports an arbitrary $t$-out-of-$n$ threshold and achieves non-interactive signing in the online phase. It relies on a new pseudorandom correlation-based offline protocol producing preprocessing material with sublinear communication complexity in the number of signatures. Both our offline and online protocols are actively secure under the Universal Composability framework. Finally, we estimate the concrete efficiency of our protocol, including an implementation of the online phase. The online protocol without network latency takes less than $15 ms$ for $t \leq 30$ and credentials sizes up to $10$. Further, our results indicate that the influence of $t$ on the online signing is insignificant, $< 6 \%$ for $t \leq 30$, and the overhead of the thresholdization occurs almost exclusively in the offline phase.



## 2023/1077

* Title: Taming Adaptivity in YOSO Protocols: The Modular Way
* Authors: Sebastian Kolby, Ran Canetti, Divya Ravi, Eduardo Soria-Vazquez, Sophia Yakoubov
* [Permalink](https://eprint.iacr.org/2023/1077)
* [Download](https://eprint.iacr.org/2023/1077.pdf)

### Abstract

YOSO-style MPC protocols (Gentry et al., Crypto'21), are a promising framework where the overall computation is partitioned into small, short-lived pieces, delegated to subsets of one-time stateless parties. Such protocols enable gaining from the security benefits provided by using a large community of participants where "mass corruption" of a large fraction of participants is considered unlikely, while keeping the computational and communication costs manageable. However, fully realizing and analyzing YOSO-style protocols has proven to be challenging: While different components have been defined and realized in various works, there is a dearth of protocols that have reasonable efficiency and enjoy full end to end security against adaptive adversaries.

The YOSO model separates the protocol design, specifying the short-lived responsibilities, from the mechanisms assigning these responsibilities to machines participating in the computation. These protocol designs must then be translated to run directly on the machines, while preserving security guarantees. We provide a versatile and modular framework for analyzing the security of YOSO-style protocols, and show how to use it to compile any protocol design that is secure against static corruptions of $t$ out of $c$ parties, into protocols that withstand adaptive corruption of $T$ out of $N$ machines (where $T/N$ is closely related to $t/c$, specifically when $t/c<0.5$, we tolerate $T/N \leq 0.29$) at overall communication cost that is comparable to that of the traditional protocol even when $c << N$.

Furthermore, we demonstrate how to minimize the use of costly non-committing encryption, thereby keeping the computational and communication overhead manageable even in practical terms, while still providing end to end security analysis. Combined with existing approaches for transforming stateful protocols into stateless ones while preserving static security (e.g. Gentry et al. 21, Kolby et al. 22), we obtain end to end security.



## 2023/1078

* Title: Bypassing Android isolation with fuel gauges: new risks with advanced power ICs
* Authors: Vincent Giraud, David Naccache
* [Permalink](https://eprint.iacr.org/2023/1078)
* [Download](https://eprint.iacr.org/2023/1078.pdf)

### Abstract

Efficient power management is critical for embedded devices, both for extending their lifetime and ensuring safety. However, this can be a challenging task due to the unpredictability of the batteries commonly used in such devices. To address this issue, dedicated Integrated Circuits known as "fuel gauges" are often employed outside of the System-On-Chip. These devices provide various metrics about the available energy source and are highly accurate. However, their precision can also be exploited by malicious actors to compromise platform confidentiality if the Operating System fails to intervene. Depending on the fuel gauge and OS configuration, several attack scenarios are possible. In this article, we focus on Android and demonstrate how it is possible to bypass application isolation to recover PINs entered in other processes.



## 2023/1079

* Title: Foundations of Data Availability Sampling
* Authors: Mathias Hall-Andersen, Mark Simkin, Benedikt Wagner
* [Permalink](https://eprint.iacr.org/2023/1079)
* [Download](https://eprint.iacr.org/2023/1079.pdf)

### Abstract

Towards building more scalable blockchains, an approach known as data availability sampling (DAS) has emerged over the past few years.
Even large blockchains like Ethereum are planning to eventually deploy DAS to improve their scalability.
In a nutshell, DAS allows the participants of a network to ensure the full availability of some data without any one participant downloading it entirely.
Despite the significant practical interest that DAS has received, there are currently no formal definitions for this primitive, no security notions, and no security proofs for any candidate constructions.
For a cryptographic primitive that may end up being widely deployed in large real-world systems, this is a rather unsatisfactory state of affairs.

In this work, we initiate a cryptographic study of data availability sampling.
To this end, we define data availability sampling precisely as a clean cryptographic primitive.
Then, we show how data availability sampling relates to erasure codes.
We do so by defining a new type of commitment schemes which naturally generalizes vector commitments and polynomial commitments.
Using our framework, we analyze existing constructions and prove them secure.
In addition, we give new constructions which are based on weaker assumptions, computationally more efficient, and do not rely on a trusted setup, at the cost of slightly larger communication complexity.
Finally, we evaluate the trade-offs of the different constructions.



## 2023/1080

* Title: ACORN-QRE: Specification and Analysis of a Method of Generating Secure One-time Pads for Use in Encryption
* Authors: Roy S Wikramaratna
* [Permalink](https://eprint.iacr.org/2023/1080)
* [Download](https://eprint.iacr.org/2023/1080.pdf)

### Abstract

REAMC Report-007(2023)
ACORN-QRE: Specification and Analysis of a Method of Generating Secure One-time Pads for Use in Encryption
Roy S Wikramaratna (email: rwikra...@gmail.com)
Abstract

The Additive Congruential Random Number (ACORN) generator is straightforward to implement; it has been demonstrated in previous papers to give rise to sequences with long period which can be proven from theoretical considerations to approximate to being uniform in up to k dimensions (for any given k).

The ACORN-QRE algorithm is a straightforward modification of ACORN which effectively avoids the linearity of the original algorithm, while preserving the uniformity of the modified sequence. It provides a new method for generating one-time pads that are resistant to attack either by current computers or by future computing developments, including quantum computers. The pads can use any alphabet (including both binary and alphanumeric) and can be used with a Vernam-type cypher to securely encrypt both files and communications.

This report explains how the ACORN-QRE algorithm works and provides evidence for the claim that the resulting one-time pads are inherently not susceptible to cryptanalysis and that they will remain secure against foreseeable developments in computing, including the potential development of quantum computers.

The ACORN-QRE algorithm is patented in the UK under Patent No. GB2591467; patent applied for in the US under Application No. 17/795632. The patents are owned by REAMC Limited, 4 Nuthatch Close, Poole, Dorset BH17 7XR, United Kingdom



## 2023/1081

* Title: ARITHMETIZATION-ORIENTED APN FUNCTIONS
* Authors: Lilya Budaghyan, Mohit Pal
* [Permalink](https://eprint.iacr.org/2023/1081)
* [Download](https://eprint.iacr.org/2023/1081.pdf)

### Abstract

Recently, many cryptographic primitives such as homomorphic encryption (HE), multi-party computation (MPC) and zero-knowledge (ZK) protocols have been proposed in the literature which operate on prime field $\mathbb{F}_p$ for some large prime $p$. Primitives that are designed using such operations are called arithmetization-oriented primitives. As the concept of arithmetization-oriented primitives is new, a rigorous cryptanalysis of such primitives is yet to be done. In this paper, we investigate arithmetization-oriented APN functions. More precisely, we investigate APN permutations in the CCZ-classes of known families of APN power functions over prime field $\mathbb{F}_p$. Moreover, we present a new class of APN binomials over $\mathbb{F}_q$ obtained by modifying the planar function $x^2$ over $\mathbb{F}_q$. We also present a class of binomials having differential uniformity at most $5$ defined via the quadratic character over finite fields of odd characteristic. We give sufficient conditions for which this family of binomials is permutation. Computationally it is confirmed that the latter family contains new APN functions for some small parameters. We conjecture it to contain an infinite subfamily of APN functions.



## 2023/1082

* Title: Intmax2: A ZK-rollup with Minimal Onchain Data and Computation Costs Featuring Decentralized Aggregators
* Authors: Erik Rybakken, Leona Hioki, Mario Yaksetig
* [Permalink](https://eprint.iacr.org/2023/1082)
* [Download](https://eprint.iacr.org/2023/1082.pdf)

### Abstract

We present a novel stateless zero-knowledge rollup (ZK-rollup) protocol with client-side validation called Intmax2. Our architecture distinctly diverges from existing ZK-rollup approaches since essentially all of the data availability and computational costs are shifted to the client-side as opposed to imposing heavy computational requirements on the rollup aggregators. Moreover, the data storage and computation in our approach is parallelizable for each user. Therefore, there are no specific nodes to validate the contents of transactions. In effect, only block producers, who periodically submit a Merkle tree root containing all the transactions, are necessary.



## 2023/1083

* Title: Keyed Sum of Permutations: a simpler RP-based PRF
* Authors: Ferdinand Sibleyras, Yosuke Todo
* [Permalink](https://eprint.iacr.org/2023/1083)
* [Download](https://eprint.iacr.org/2023/1083.pdf)

### Abstract

Idealized constructions in cryptography prove the security of a primitive based on the security of another primitive.
The challenge of building a pseudorandom function (PRF) from a random permutation (RP) has only been recently tackled by Chen, Lambooij and Mennink [CRYPTO 2019] who proposed Sum of Even-Mansour (SoEM) with a provable beyond-birthday-bound security.
In this work, we revisit the challenge of building a PRF from an RP.
On the one hand, we describe Keyed Sum of Permutations (KSoP) that achieves the same provable security as SoEM while being strictly simpler since it avoids a key addition but still requires two independent keys and permutations.
On the other hand, we show that it is impossible to further simplify the scheme by deriving the two keys with a simple linear key schedule as it allows a non-trivial birthday-bound key recovery attack.
The birthday-bound attack is mostly information-theoretic, but it can be optimized to run faster than a brute-force attack.



## 2023/1084

* Title: A Side-Channel Attack on a Masked Hardware Implementation of CRYSTALS-Kyber
* Authors: Yanning Ji, Elena Dubrova
* [Permalink](https://eprint.iacr.org/2023/1084)
* [Download](https://eprint.iacr.org/2023/1084.pdf)

### Abstract

NIST has recently selected CRYSTALS-Kyber as a new public key encryption and key establishment algorithm to be standardized. This makes it important to evaluate the resistance of CRYSTALS-Kyber implementations to side-channel attacks. Software implementations of CRYSTALS-Kyber have already been thoroughly analysed. The discovered vulnerabilities helped improve the subsequently released versions and promoted stronger countermeasures against side-channel attacks. In this paper, we present the first attack on a protected hardware implementation of CRYSTALS-Kyber. We demonstrate a practical message (shared key) recovery attack on the first-order masked FPGA implementation of Kyber-512 by Kamucheka et al. (2022) using power analysis based on the Hamming distance leakage model. The presented attack exploits a vulnerability located in the masked message decoding procedure which is called during the decryption step of the decapsulation. The message recovery is performed using a profiled deep learning-based method which extracts the message directly, without extracting each share explicitly. By repeating the same decapsulation process multiple times, it is possible to increase the success rate of full shared key recovery to 99%.



## 2023/1085

* Title: Fuzzy Deduplication Scheme Supporting Pre-verification of Label Consistency
* Authors: Zehui Tang, Shengke Zeng, Tao Li, Shuai Cheng, Haoyu Zheng
* [Permalink](https://eprint.iacr.org/2023/1085)
* [Download](https://eprint.iacr.org/2023/1085.pdf)

### Abstract

Efficiently and securely removing encrypted redundant data with cross-user in the cloud is challenging. Convergent Encryption (CE) is difficult to resist dictionary attacks for its deterministic tag. Server-aided mechanism is against such attacks while it may exist collusion. Focus on multimedia data, this paper proposes an efficient and secure fuzzy deduplication system without any additional servers. We also propose a notion of preverification of label consistency to compensate for the irreparable post-verification loss. Compared with other fuzzy deduplication schemes, our work has apparent advantages in deduplication efficiency and security based on a natural data set.



## 2023/1086

* Title: On One-way Functions and the Worst-case Hardness of Time-Bounded Kolmogorov Complexity
* Authors: Yanyi Liu, Rafael Pass
* [Permalink](https://eprint.iacr.org/2023/1086)
* [Download](https://eprint.iacr.org/2023/1086.pdf)

### Abstract

Whether one-way functions (OWF) exist is arguably the most important
problem in Cryptography, and beyond. While lots of candidate
constructions of one-way functions are known, and recently also
problems whose average-case hardness characterize the existence of
OWFs have been demonstrated, the question of
whether there exists some \emph{worst-case hard problem} that characterizes
the existence of one-way functions has remained open since their
introduction in 1976.

In this work, we present the first ``OWF-complete'' promise
problem---a promise problem whose worst-case hardness w.r.t. $\BPP$
(resp. $\Ppoly$) is \emph{equivalent} to the existence of OWFs secure
against $\PPT$ (resp. $\nuPPT$) algorithms. The problem is a
variant of the Minimum Time-bounded Kolmogorov Complexity
problem ($\mktp[s]$ with a threshold $s$), where we condition on
instances having small ``computational depth''.

We furthermore show that depending on the choice of the
threshold $s$, this problem characterizes either ``standard''
(polynomially-hard) OWFs, or quasi polynomially- or
subexponentially-hard OWFs. Additionally, when the threshold is
sufficiently small (e.g., $2^{O(\sqrt{n})}$ or $\poly\log n$) then
\emph{sublinear} hardness of this problem suffices to characterize
quasi-polynomial/sub-exponential OWFs.

While our constructions are black-box, our analysis is \emph{non-
black box}; we additionally demonstrate that fully black-box constructions
of OWF from the worst-case hardness of this problem are impossible.
We finally show that, under Rudich's conjecture, and standard derandomization
assumptions, our problem is not inside $\coAM$; as such, it
yields the first candidate problem believed to be outside of $\AM \cap \coAM$,
or even ${\bf SZK}$, whose worst case hardness implies the existence of OWFs.



## 2023/1087

* Title: Moving a Step of ChaCha in Syncopated Rhythm
* Authors: Shichang Wang, Meicheng Liu, Shiqi Hou, Dongdai Lin
* [Permalink](https://eprint.iacr.org/2023/1087)
* [Download](https://eprint.iacr.org/2023/1087.pdf)

### Abstract

The stream cipher ChaCha is one of the most widely used ciphers in the real world, such as in TLS, SSH and so on. In this paper, we study the security of ChaCha via differential cryptanalysis based on probabilistic neutrality bits (PNBs). We introduce the \textit{syncopation} technique for the PNB-based approximation in the backward direction, which significantly amplifies its correlation by utilizing the property of ARX structure. In virtue of this technique, we present a new and efficient method for finding a good set of PNBs. A refined framework of key-recovery attack is then formalized for round-reduced ChaCha. The new techniques allow us to break 7.5 rounds of ChaCha without the last XOR and rotation, as well as to bring faster attacks on 6 rounds and 7 rounds of ChaCha.



## 2023/1088

* Title: Building Hard Problems by Combining Easy Ones
* Authors: Riddhi Ghosal, Amit Sahai
* [Permalink](https://eprint.iacr.org/2023/1088)
* [Download](https://eprint.iacr.org/2023/1088.pdf)

### Abstract

In this work, we initiate a new conceptual line of attack on the fundamental question of how to generate hard problems. Motivated by the need for one-way functions in cryptography, we propose an information-theoretic framework to study the question of generating new provably hard one-way functions by composing functions that are easy to invert and evaluate, where each such easy function is modeled as a random oracles paired with another oracle that implements an inverse function.



## 2023/1089

* Title: Security-Performance Tradeoff in DAG-based Proof-of-Work Blockchain Protocols
* Authors: Shichen Wu, Puwen Wei, Ren Zhang, Bowen Jiang
* [Permalink](https://eprint.iacr.org/2023/1089)
* [Download](https://eprint.iacr.org/2023/1089.pdf)

### Abstract

Proof-of-work (PoW) blockchain protocols based on directed acyclic graphs (DAGs) have demonstrated superior transaction confirmation performance compared to their chain-based predecessors. However, it is uncertain whether their security deteriorates in high-throughput settings similar to their predecessors, because their acceptance of simultaneous blocks and complex block dependencies presents challenges for rigorous security analysis.

We address these challenges by analyzing DAG-based protocols via a congestible blockchain model (CBM), a general model that allows case-by-case upper bounds on the block propagation delay, rather than a uniform upper bound as in most previous analyses. CBM allows us to capture two key phenomena of high-throughput settings: (1) simultaneous blocks increase each other's propagation delay, and (2) a block can be processed only after receiving all the blocks it refers to. We further devise a reasonable adversarial block propagation strategy in CBM, called the late-predecessor attack, which exploits block dependencies to delay the processing of honest blocks. We then evaluate the security and performance of Prism and OHIE, two DAG-based protocols that aim to break the security-performance tradeoff, in the presence of an attacker capable of launching the late predecessor attack. Our results show that these protocols suffer from reduced security and extended latency in high-throughput settings similar to their chain-based predecessors.



## 2023/1090

* Title: Bulletproofs With Stochastic Equation Sets
* Authors: Michael Brand, Benoit Poletti
* [Permalink](https://eprint.iacr.org/2023/1090)
* [Download](https://eprint.iacr.org/2023/1090.pdf)

### Abstract

Bulletproofs are general-purpose Zero Knowledge Proof protocols that allow a Prover to demonstrate to a Verifier knowledge of a solution to a set of equations, represented as a Rank 1 Constraint System.

We present a protocol extending the standard Bulletproof protocol, which introduces a second layer of interactivity to the protocol, by allowing the Verifier to choose the set of equations after the Prover has already committed to portions of the solution.

We show that such Verifier-chosen (or stochastically-chosen) equation sets can be used to design smaller equation sets with less variables that have the same proving-power as their larger, deterministic counterparts but are, in practice, orders of magnitude faster both in proof generation and in proof verification, and even reduce the size of the resulting proofs. We demonstrate this with an example from a real-world application.

Our method maintains all the classical benefits of the Bulletproof approach: efficient proof generation, efficient proof checking, extremely short proofs, and the ability to use Fiat-Shamir challenges in order to turn an interactive proof into a non-interactive proof.



## 2023/1091

* Title: On Derandomizing Yao's Weak-to-Strong OWF Construction
* Authors: Chris Brzuska, Geoffroy Couteau, Pihla Karanko, Felix Rohrbach
* [Permalink](https://eprint.iacr.org/2023/1091)
* [Download](https://eprint.iacr.org/2023/1091.pdf)

### Abstract

The celebrated result of Yao (FOCS'82) shows that concatenating $n\cdot p(n)$ copies of a weak one-way function (OWF) $f$, which can be inverted with probability $1-\tfrac{1}{p(n)}$, yields a strong OWF $g$, showing that weak and strong OWFs are black-box equivalent. Yao's transformation is not security-preserving, i.e., the input to $g$ needs to be much larger than the input to $f$. Understanding whether a larger input is inherent is a long-standing open question.

In this work, we explore necessary features of constructions which achieve short input length by proving the following: for any direct product construction of a strong OWF $g$ from a weak OWF $f$, which can be inverted with probability $1-\tfrac{1}{p(n)}$, the input size of $g$ must grow as $\Omega(p(n))$. Here, direct product refers to the following structure: the construction $g$ executes some arbitrary pre-processing function (independent of $f$) on its input $s$, obtaining a vector $(x_1, \cdots, x_l)$, and outputs $f(x_1), \cdots, f(x_l)$. When setting the pre-processing to be the identity, one recovers thus Yao's construction.

Our result generalizes to functions $g$ with post-processing, as long as the post-processing function is not too lossy. Thus, in essence, any weak-to-strong OWF hardness amplification must either (1) be very far from security-preserving, (2) use adaptivity, or (3) must be very far from a direct-product structure (in the sense that post-processing of the outputs of $f$ is very lossy).

On a technical level, we use ideas from lower bounds for secret-sharing to prove the impossibility of derandomizing Yao in a black-box way. Our results are in line with Goldreich, Impagliazzo, Levin, Venkatesan, and Zuckerman (FOCS 1990) who derandomize Yao's construction for regular weak OWFs by evaluating the OWF along a random walk on an expander graph – the construction is adaptive, since it alternates steps on the expander graph with evaluations of the weak OWF.



## 2023/1092

* Title: Adaptive attack for FESTA
* Authors: Tomoki Moriya
* [Permalink](https://eprint.iacr.org/2023/1092)
* [Download](https://eprint.iacr.org/2023/1092.pdf)

### Abstract

Isogeny-based cryptography is one of the candidates for post-quantum cryptography. In 2023, Kani's theorem breaks some isogeny-based schemes including SIDH, which was considered as a promising post-quantum scheme. Though Kani's theorem damaged isogeny-based cryptography, some researchers try to dig into the applications of Kani's theorem. FESTA is an isogeny-based trapdoor function that is one trial to apply Kani's theorem to cryptography.

In this paper, we provide an adaptive attack for a possible PKE scheme based on FESTA trapdoor functions. Our attack reveals the secret key of the function. Our attack may be used if the recipient of the PKE scheme does not check whether the hidden matrix corresponding to the ciphertext is correct. In other words, the recipient can prevent our attack by checking the correctness of the matrix.



## 2023/1093

* Title: Lattice Isomorphism as a Group Action and Hard Problems on Quadratic Forms
* Authors: Alessandro Budroni, Jesús-Javier Chi-Domínguez, Mukul Kulkarni
* [Permalink](https://eprint.iacr.org/2023/1093)
* [Download](https://eprint.iacr.org/2023/1093.pdf)

### Abstract

Group actions have been used as a foundation in Public-key Cryptography to provide a framework for hard problems and assumptions. In this work we formalize the Lattice Isomorphism Problem (LIP) within the context of cryptographic group actions. Our main result shows that a quadratic number of queries to a randomized oracle outputting LIP instances sharing the same secret is enough for inverting the group action in polynomial time. We use this result to uncover a family of weak isomorphisms and to derive two new hard problems on quadratic forms equivalent to LIP for the case of lattices with trivial automorphism.