[digest] 2023 Week 21

[IACR ePrint Archive]

## In this issue

1. [2023/705] Deniable Cryptosystems: Simpler Constructions and ...
2. [2023/713] KAIME : Central Bank Digital Currency with ...
3. [2023/714] A Two-Party Hierarchical Deterministic Wallets in ...
4. [2023/715] Research Philosophy of Modern Cryptography
5. [2023/716] Towards High-speed ASIC Implementations of Post- ...
6. [2023/717] Generic Error SDP and Generic Error CVE
7. [2023/718] Zero-Knowledge Proofs from the Action Subgraph
8. [2023/719] Lower Bounds for Lattice-based Compact Functional ...
9. [2023/720] MUSES: Efficient Multi-User Searchable Encrypted ...
10. [2023/721] A Fast RLWE-Based IPFE Library and its Application ...
11. [2023/722] Composing Bridges
12. [2023/723] Non-Interactive Commitment from Non-Transitive ...
13. [2023/724] Not so Difficult in the End: Breaking the ASCADv2 ...
14. [2023/725] On Perfect Linear Approximations and Differentials ...
15. [2023/726] A Note on ``A Secure Anonymous D2D Mutual ...
16. [2023/727] Safeguarding Physical Sneaker Sale Through a ...
17. [2023/728] SoK: Distributed Randomness Beacons
18. [2023/729] Compact Lattice Gadget and Its Applications to ...
19. [2023/730] The Problem of Half Round Key XOR
20. [2023/731] Fast Exhaustive Search for Polynomial Systems over F3
21. [2023/732] VerifMSI: Practical Verification of Hardware and ...
22. [2023/733] On implemented graph based generator of ...
23. [2023/734] TLS → Post-Quantum TLS: Inspecting the TLS ...
24. [2023/735] Privacy-preserving Attestation for Virtualized ...
25. [2023/736] Private Eyes: Zero-Leakage Iris Searchable Encryption
26. [2023/737] Differential properties of integer multiplication
27. [2023/738] Extremal algebraic graphs, quadratic multivariate ...
28. [2023/739] SMAUG: Pushing Lattice-based Key Encapsulation ...
29. [2023/740] Practical Robust DKG Protocols for CSIDH
30. [2023/741] The Referendum Problem in Anonymous Voting for ...
31. [2023/742] Finding Desirable Substitution Box with SASQUATCH
32. [2023/743] On Sustainable Ring-based Anonymous Systems
33. [2023/744] On Extremal Algebraic Graphs and implementations of ...
34. [2023/745] PSI from ring-OLE
35. [2023/746] Homomorphic Signatures for Subset and Superset ...
36. [2023/747] Key-Range Attribute-Based Signatures for Range of ...
37. [2023/748] Towards the Links of Cryptanalytic Methods on ...
38. [2023/749] Note on Subversion-Resilient Key Exchange
39. [2023/750] BAKSHEESH: Similar Yet Different From GIFT
40. [2023/751] Scalable Agreement Protocols with Optimal ...
41. [2023/752] Schnorr protocol in Jasmin
42. [2023/753] A Faster Software Implementation of SQISign
43. [2023/754] Batch Proofs are Statistically Hiding
44. [2023/755] The security of Kyber's FO-transform
45. [2023/756] SDitH in the QROM

## 2023/705

* Title: Deniable Cryptosystems: Simpler Constructions and Achieving Leakage Resilience
* Authors: Zhiyuan An, Haibo Tian, Chao Chen, Fangguo Zhang
* [Permalink](https://eprint.iacr.org/2023/705)
* [Download](https://eprint.iacr.org/2023/705.pdf)

### Abstract

Deniable encryption (Canetti et al. CRYPTO ’97) is an intriguing primitive, which provides security guarantee against coercion by allowing a sender to convincingly open the ciphertext into a fake message. Despite the notable result by Sahai and Waters STOC ’14 and other efforts in functionality extension, all the deniable public key encryption (DPKE) schemes suffer from intolerable overhead due to the heavy building blocks, e.g., translucent sets or indistinguishability obfuscation. Besides, none of them considers the possible damage from leakage in the real world, obstructing these protocols from practical use.
To fill the gap, in this work we first present a simple and generic approach of sender-DPKE from ciphertext-simulatable encryption, which can be instantiated with nearly all the common PKE schemes. The core of this design is a newly-designed framework for flipping a bit-string that offers inverse polynomial distinguishability. Then we theoretically expound and experimentally show how classic side-channel attacks (timing or simple power attacks), can help the coercer to break deniability, along with feasible countermeasures.



## 2023/713

* Title: KAIME : Central Bank Digital Currency with Realistic and Modular Privacy
* Authors: Ali Dogan, Kemal Bicakci
* [Permalink](https://eprint.iacr.org/2023/713)
* [Download](https://eprint.iacr.org/2023/713.pdf)

### Abstract

Recently, with the increasing interest in Central Bank Digital Currency (CBDC), many countries have been working on researching and developing digital currency. The most important reasons for this interest are that CBDC eliminates the disadvantages of traditional currencies and provides a safer, faster, and more efficient payment system. These benefits also come with challenges, such as safeguarding individuals’ privacy and ensuring regulatory mechanisms. While most researches address the privacy conflict between users and regulatory agencies, they miss an important detail. Important parts of a financial system are banks and financial institutions. Some studies ignore the need for privacy and include these institutions in the CBDC system, no system currently offers a solution to the privacy conflict between banks, financial institutions, and users. In this study, while we offer a solution to the privacy conflict between the user and the regulatory agencies, we also provide a solution to the privacy conflict between the user and the banks. Our solution, KAIME has also a modular structure. The privacy of the sender and receiver can be hidden if desired. Compared to previous related research, security analysis and implementation of KAIME is substantially simpler because simple and well-known cryptographic methods are used.



## 2023/714

* Title: A Two-Party Hierarchical Deterministic Wallets in Practice
* Authors: ChihYun Chuang, IHung Hsu, TingFang Lee
* [Permalink](https://eprint.iacr.org/2023/714)
* [Download](https://eprint.iacr.org/2023/714.pdf)

### Abstract

The applications of Hierarchical Deterministic Wallet are rapidly growing in various areas such as cryptocurrency exchanges and hardware wallets. Improving privacy and security is more important than ever. In this study, we proposed a protocol that fully support a two-party computation of BIP32. Our protocol, similar to the distributed key generation, can generate each party’s secret share, the common chain-code, and the public key without revealing a seed and any descendant private keys. We also provided a simulation-based proof of our protocol assuming a rushing, static, and malicious adversary in the hybrid model. Our master key generation protocol produces up to total of two bit leakages from a honest party given the feature that the seeds will be re-selected after each execution. The proposed hardened child key derivation protocol leads up to a one bit leakage in the worst situation of simulation from a honest party and will be accumulated with each execution. Fortunately, in reality, this issue can be largely mitigated by adding some validation criteria of boolean circuits and masking the input shares before each execution. We then implemented the proposed protocol and ran in a single thread on a laptop which turned out with practically acceptable execution time. Lastly, the outputs of our protocol can be easily integrated with many threshold sign protocols.



## 2023/715

* Title: Research Philosophy of Modern Cryptography
* Authors: Fuchun Guo, Willy Susilo, Xiaofeng Chen, Peng Jiang, Jianchang Lai, Zhen Zhao
* [Permalink](https://eprint.iacr.org/2023/715)
* [Download](https://eprint.iacr.org/2023/715.pdf)

### Abstract

Proposing novel cryptography schemes (e.g., encryption, signatures, and protocols) is one of the main research goals in modern cryptography. In this paper, based on more than 800 research papers since 1976 that we have surveyed, we introduce the research philosophy of cryptography behind these papers. We use ``benefits" and ``novelty" as the keywords to introduce the research philosophy of proposing new schemes, assuming that there is already one scheme proposed for a cryptography notion. Next, we introduce how benefits were explored in the literature and we have categorized the methodology into 3 ways for benefits, 6 types of benefits, and 17 benefit areas. As examples, we introduce 40 research strategies within these benefit areas that were invented in the literature. The introduced research strategies have covered most cryptography schemes published in top-tier cryptography conferences.



## 2023/716

* Title: Towards High-speed ASIC Implementations of Post-Quantum Cryptography
* Authors: Malik Imran, Aikata Aikata, Sujoy Sinha Roy, Samuel pagliarini
* [Permalink](https://eprint.iacr.org/2023/716)
* [Download](https://eprint.iacr.org/2023/716.pdf)

### Abstract

In this brief, we realize different architectural techniques towards improving the performance of post-quantum cryptography (PQC) algorithms when implemented as hardware accelerators on an application-specific integrated circuit (ASIC) platform. Having SABER as a case study, we designed a 256-bit wide architecture geared for high-speed cryptographic applications that incorporates smaller and distributed SRAM memory blocks. Moreover, we have adapted the building blocks of SABER to process 256-bit words. We have also used a buffer technique for efficient polynomial coefficient multiplications to reduce the clock cycle count. Finally, double-sponge functions are combined serially (one after another) in a high-speed KECCAK core to improve the hash operations of SHA/SHAKE. For key-generation, encapsulation, and decapsulation operations of SABER, our 256-bit wide accelerator with a single sponge function is 1.71x, 1.45x, and 1.78x faster compared to the raw clock cycle count of a serialized SABER design. Similarly, our 256-bit implementation with double-sponge functions takes 1.08x, 1.07x & 1.06x fewer clock cycles compared to its single-sponge counterpart. The studied optimization techniques are not specific to SABER - they can be utilized for improving the performance of other lattice-based PQC accelerators.



## 2023/717

* Title: Generic Error SDP and Generic Error CVE
* Authors: Felice Manganiello, Freeman Slaughter
* [Permalink](https://eprint.iacr.org/2023/717)
* [Download](https://eprint.iacr.org/2023/717.pdf)

### Abstract

This paper introduces a new family of CVE schemes built from generic errors (GE-CVE) and identifies a vulnerability therein. To introduce the problem, we generalize the concept of error sets beyond those defined by a metric, and use the set-theoretic difference operator to characterize when these error sets are detectable or correctable by codes. We prove the existence of a general, metric-less form of the Gilbert-Varshamov bound, and show that - like in the Hamming setting - a random code corrects a generic error set with overwhelming probability. We define the generic error SDP (GE-SDP), which is contained in the complexity class of NP-hard problems, and use its hardness to demonstrate the security of GE-CVE. We prove that these schemes are complete, sound, and zero-knowledge. Finally, we identify a vulnerability of the GE-SDP for codes defined over large extension fields and without a very high rate. We show that certain GE-CVE parameters suffer from this vulnerability, notably the restricted CVE scheme.



## 2023/718

* Title: Zero-Knowledge Proofs from the Action Subgraph
* Authors: Giacomo Borin, Edoardo Persichetti, Paolo Santini
* [Permalink](https://eprint.iacr.org/2023/718)
* [Download](https://eprint.iacr.org/2023/718.pdf)

### Abstract

In this work, we describe a technique to amplify the soundness of zero-knowledge proofs of knowledge for cryptographic group actions.



## 2023/719

* Title: Lower Bounds for Lattice-based Compact Functional Encryption
* Authors: Erkan Tairi, Akın Ünal
* [Permalink](https://eprint.iacr.org/2023/719)
* [Download](https://eprint.iacr.org/2023/719.pdf)

### Abstract

Functional encryption (FE) is a primitive where the holder of a master secret key can control which functions a user can evaluate on encrypted data. It is a powerful primitive that even implies indistinguishability obfuscation (iO), given sufficiently compact ciphertexts (Ananth-Jain, CRYPTO'15 and Bitansky-Vaikuntanathan, FOCS'15). However, despite being extensively studied, there are FE schemes, such as function-hiding inner-product FE (Bishop-Jain-Kowalczyk, AC'15, Abdalla-Catalano-Fiore-Gay-Ursu, CRYPTO’18) and compact quadratic FE (Baltico-Catalano-Fiore-Gay, Lin, CRYPTO’17), that can be only realized using pairings. This raises whether there are some mathematical barriers which hinder us from realizing these FE schemes from other assumptions.

In this paper, we study the difficulty of constructing lattice-based compact FE. We generalize the impossibility results of Ünal (EC'20) for lattice-based function-hiding FE, and extend it to the case of compact FE. Concretely, we prove lower bounds for lattice-based compact FE schemes which meet some (natural) algebraic restrictions at encryption and decryption, and have messages and ciphertexts of constant dimensions. We see our results as important indications of why it is hard to construct lattice-based FE schemes for new functionalities, and which mathematical barriers have to be overcome.



## 2023/720

* Title: MUSES: Efficient Multi-User Searchable Encrypted Database
* Authors: Tung Le, Rouzbeh Behnia, Jorge Guajardo, Thang Hoang
* [Permalink](https://eprint.iacr.org/2023/720)
* [Download](https://eprint.iacr.org/2023/720.pdf)

### Abstract

Searchable encrypted systems enable privacy-preserving keyword search on encrypted data. Symmetric Searchable Encryption (SSE) achieves high security (e.g., forward privacy) and efficiency (i.e., sublinear search), but it only supports single-user. Public Key Searchable Encryption (PEKS) supports multi-user settings, however, it suffers from inherent security limitations such as being vulnerable to keyword-guessing attacks and the lack of forward privacy. Recent work has combined SSE and PEKS to achieve the best of both worlds: support multi-user settings, provide forward privacy while having sublinear complexity. However, despite their elegant design, the existing hybrid scheme inherits some of the security limitations of the underlying paradigms (e.g., patterns leakage, keyword-guessing) and might not be suitable for certain applications due to costly public-key operations (e.g., bilinear pairing). In this paper, we propose MUSES, a new multi-user encrypted search scheme that addresses the limitations in the existing hybrid design, while offering user efficiency. Specifically, MUSES permits multi-user functionalities (reader/writer separation, permission revocation), prevents keyword-guessing attacks, protects search/result patterns, achieves forward/backward privacy, and features minimal user overhead. In MUSES, we demonstrate a unique incorporation of various state-of-the-art distributed cryptographic protocols including Distributed Point Function, Distributed PRF, and Secret-Shared Shuffle. We also introduce a new oblivious shuffle protocol for the general 𝐿-party setting with dishonest majority, which can be of independent interest. Our experimental results indicated that the keyword search in our scheme is two orders of magnitude faster with 13× lower user bandwidth overhead than the state-of-the-art.



## 2023/721

* Title: A Fast RLWE-Based IPFE Library and its Application to Privacy-Preserving Biometric Authentication
* Authors: Supriya Adhikary, Angshuman Karmakar
* [Permalink](https://eprint.iacr.org/2023/721)
* [Download](https://eprint.iacr.org/2023/721.pdf)

### Abstract

With the increased use of data and communication through the internet and the abundant misuse of personal data by many organizations, people are more sensitive about their privacy. Privacy-preserving computation is becoming increasingly important in this era. Functional encryption allows a user to evaluate a function on encrypted data without revealing sensitive information. Most implementations of functional encryption schemes are too time-consuming for practical use. Mera et al. first proposed an inner product functional encryption scheme based on ring learning with errors to improve efficiency. In this work, we optimize the implementation of their work and propose a fast inner product functional encryption library. Specifically, we identify the main performance bottleneck, which is the number theoretic transformation based polynomial multiplication used in the scheme. We also identify the micro and macro level parallel components of the scheme and propose novel techniques to improve the efficiency using $\textit{open multi-processing}$ and $\textit{advanced vector extensions 2}$ vector processor. Compared to the original implementation, our optimization methods translate to $89.72\%$, $83.06\%$, $59.30\%$, and $53.80\%$ improvements in the $\textbf{Setup}$, $\textbf{Encrypt}$, $\textbf{KeyGen}$, and $\textbf{Decrypt}$ operations respectively, in the scheme for standard security level. Designing privacy-preserving applications using functional encryption is ongoing research. Therefore, as an additional contribution to this work, we design a privacy-preserving biometric authentication scheme using inner product functional encryption primitives.



## 2023/722

* Title: Composing Bridges
* Authors: Mugurel Barcau, Vicentiu Pasol, George C Turcas
* [Permalink](https://eprint.iacr.org/2023/722)
* [Download](https://eprint.iacr.org/2023/722.pdf)

### Abstract

The present work builds on previous investigations of the authors (and their collaborators) regarding bridges, a certain type of morphisms between encryption schemes, making a step forward in developing a (category theory) language for studying relations between encryption schemes. Here we analyse the conditions under which bridges can be performed sequentially, formalizing the notion of composability. One of our results gives a sufficient condition for a pair of bridges to be composable. We illustrate that composing two bridges, each independently satisfying a previously established IND-CPA security definition, can actually lead to an insecure bridge. Our main result gives a sufficient condition that a pair of secure composable bridges should satisfy in order for their composition to be a secure bridge. We also introduce the concept of a complete bridge and show that it is connected to the notion of Fully composable Homomorphic Encryption (FcHE), recently considered by Micciancio. Moreover, we show that a result of Micciancio which gives a construction of FcHE schemes can be phrased in the language of complete bridges, where his insights can be formalised in a greater generality.



## 2023/723

* Title: Non-Interactive Commitment from Non-Transitive Group Actions
* Authors: Giuseppe D'Alconzo, Andrea Flamini, Andrea Gangemi
* [Permalink](https://eprint.iacr.org/2023/723)
* [Download](https://eprint.iacr.org/2023/723.pdf)

### Abstract

Group actions are becoming a viable option for post-quantum cryptography assumptions. Indeed, in recent years some works have shown how to construct primitives from assumptions based on isogenies of elliptic curves, such as CSIDH, on tensors or on code equivalence problems. This paper presents a bit commitment scheme, built on non-transitive group actions, which is shown to be secure in the standard model, under the decisional Group Action Inversion Problem. In particular, the commitment is computationally hiding and perfectly binding, and is obtained from a novel and general framework that exploits the properties of some orbit-invariant functions, together with group actions. Previous constructions depend on an interaction between the sender and the receiver in the commitment phase, which results in an interactive bit commitment. We instead propose the first non-interactive bit commitment based on group actions. Then we show that, when the sender is honest, the constructed commitment enjoys an additional feature, i.e., it is possible to tell whether two commitments were obtained from the same input, without revealing the input. We define the security properties that such a construction must satisfy, and we call this primitive linkable commitment. Finally, as an example, an instantiation of the scheme using tensors with coefficients in a finite field is provided. In this case, the invariant function is the computation of the rank of a tensor, and the cryptographic assumption is related to the Tensor Isomorphism problem.



## 2023/724

* Title: Not so Difficult in the End: Breaking the ASCADv2 Dataset
* Authors: Lichao Wu, Guilherme Perin, Stjepan Picek
* [Permalink](https://eprint.iacr.org/2023/724)
* [Download](https://eprint.iacr.org/2023/724.pdf)

### Abstract

The ASCADv2 dataset ranks among the most secure publicly available datasets today. Two layers of countermeasures protect it: affine masking and shuffling, and the current attack approaches rely on strong assumptions. Specifically, besides having access to the source code, an adversary also requires prior knowledge of random shares. This paper forgoes reliance on such knowledge and proposes two attack approaches based on the vulnerabilities of the affine mask implementation. As a result, the first attack can retrieve all secret keys' reliance in less than a minute. Although the second attack is not entirely successful in recovering all keys, we believe more traces would help make such an attack fully functional.



## 2023/725

* Title: On Perfect Linear Approximations and Differentials over Two-Round SPNs
* Authors: Christof Beierle, Patrick Felke, Gregor Leander, Patrick Neumann, Lukas Stennes
* [Permalink](https://eprint.iacr.org/2023/725)
* [Download](https://eprint.iacr.org/2023/725.pdf)

### Abstract

Recent constructions of (tweakable) block ciphers with an embedded cryptographic backdoor relied on the existence of probability-one differentials or perfect (non-)linear approximations over a reduced-round version of the primitive. In this work, we study how the existence of probability-one differentials or perfect linear approximations over two rounds of a substitution-permutation network can be avoided by design. More precisely, we develop criteria on the s-box and the linear layer that guarantee the absence of probability-one differentials for all keys. We further present an algorithm that allows to efficiently exclude the existence of keys for which there exists a perfect linear approximation.



## 2023/726

* Title: A Note on ``A Secure Anonymous D2D Mutual Authentication and Key Agreement Protocol for IoT''
* Authors: Zhengjun Cao, Lihua Liu
* [Permalink](https://eprint.iacr.org/2023/726)
* [Download](https://eprint.iacr.org/2023/726.pdf)

### Abstract

We show that the key agreement scheme [Internet of Things, 2022(18): 100493] is flawed. (1) It neglects the structure of an elliptic curve and presents some false computations. (2) The scheme is insecure against key compromise impersonation attack.



## 2023/727

* Title: Safeguarding Physical Sneaker Sale Through a Decentralized Medium
* Authors: Marwan Zeggari, Aydin Abadi, Renaud Lambiotte, Mohamad Kassab
* [Permalink](https://eprint.iacr.org/2023/727)
* [Download](https://eprint.iacr.org/2023/727.pdf)

### Abstract

Sneakers were designated as the most counterfeited fashion item online, with three times more risk in a trade than any other fashion purchase. As the market expands, the current sneaker scene displays several vulnerabilities and trust flaws, mostly related to the legitimacy of assets or actors. In this paper, we investigate various blockchain-based mechanisms to address these large-scale trust issues. We argue that (i) pre-certified and tracked assets through the use of non-fungible tokens can ensure the genuine nature of an asset and authenticate its owner more effectively during peer-to-peer trading across a marketplace; (ii) a game-theoretic-based system with economic incentives for participating users can greatly reduce the rate of online fraud and address missed delivery deadlines; (iii) a decentralized dispute resolution system biased in favour of an honest party can solve potential conflicts more reliably.



## 2023/728

* Title: SoK: Distributed Randomness Beacons
* Authors: Kevin Choi, Aathira Manoj, Joseph Bonneau
* [Permalink](https://eprint.iacr.org/2023/728)
* [Download](https://eprint.iacr.org/2023/728.pdf)

### Abstract

Motivated and inspired by the emergence of blockchains, many new protocols have recently been proposed for generating publicly verifiable randomness in a distributed yet secure fashion. These protocols work under different setups and assumptions, use various cryptographic tools, and entail unique trade-offs and characteristics. In this paper, we systematize the design of distributed randomness beacons (DRBs) as well as the cryptographic building blocks they rely on. We evaluate protocols on two key security properties, unbiasability and unpredictability, and discuss common attack vectors for predicting or biasing the beacon output and the countermeasures employed by protocols. We also compare protocols by communication and computational efficiency. Finally, we provide insights on the applicability of different protocols in various deployment scenarios and highlight possible directions for further research.



## 2023/729

* Title: Compact Lattice Gadget and Its Applications to Hash-and-Sign Signatures
* Authors: Yang Yu, Huiwen Jia, Xiaoyun Wang
* [Permalink](https://eprint.iacr.org/2023/729)
* [Download](https://eprint.iacr.org/2023/729.pdf)

### Abstract

Lattice gadgets and the associated algorithms are the essential building blocks of lattice-based cryptography. In the past decade, they have been applied to build versatile and powerful cryptosystems. However, the practical optimizations and designs of gadget-based schemes generally lag their theoretical constructions.
For example, the gadget-based signatures have elegant design and capability of extending to more advanced primitives, but they are far less efficient than other lattice-based signatures.

This work aims to improve the practicality of gadget-based cryptosystems, with a focus on hash-and-sign signatures. To this end, we develop a compact gadget framework in which the used gadget is a square matrix instead of the short and fat one used in previous constructions. To work with this compact gadget, we devise a specialized gadget sampler, called semi-random sampler, to compute the approximate preimage. It first deterministically computes the error and then randomly samples the preimage. We show that for uniformly random targets, the preimage and error distributions are simulatable without knowing the trapdoor. This ensures the security of the signature applications. Compared to the Gaussian-distributed errors in previous algorithms, the deterministic errors have a smaller size, which lead to a substantial gain in security and enables a practically working instantiation.

As the applications, we present two practically efficient gadget-based signature schemes based on NTRU and Ring-LWE respectively. The NTRU-based scheme offers comparable efficiency to Falcon and Mitaka and a simple implementation without the need of generating the NTRU trapdoor. The LWE-based scheme also achieves a desirable overall performance. It not only greatly outperforms the state-of-the-art LWE-based hash-and-sign signatures, but also has an even smaller size than the LWE-based Fiat-Shamir signature scheme Dilithium. These results fill the long-term gap in practical gadget-based signatures.



## 2023/730

* Title: The Problem of Half Round Key XOR
* Authors: Anubhab Baksi
* [Permalink](https://eprint.iacr.org/2023/730)
* [Download](https://eprint.iacr.org/2023/730.pdf)

### Abstract

In the design of GIFT, half round key XOR is used. This leads to the undesired consequence that the security against the differential/linear attacks are overestimated. This comes from the observation that; in the usual DDT/LAT based analysis of the differential/linear attacks, the inherent assumption is the full round key is XORed at each round.



## 2023/731

* Title: Fast Exhaustive Search for Polynomial Systems over F3
* Authors: Bo-Yin Yang, Wei-Jeng Wang, Shang-Yi Yang, Char-Shin Miou, Chen-Mou Cheng
* [Permalink](https://eprint.iacr.org/2023/731)
* [Download](https://eprint.iacr.org/2023/731.pdf)

### Abstract

Solving multivariate polynomial systems over finite fields is an important
problem in cryptography. For random F2 low-degree systems with equally many
variables and equations, enumeration is more efficient than advanced solvers for all
practical problem sizes. Whether there are others remained an open problem.
We here study and propose an exhaustive-search algorithm for low degrees systems
over F3 which is suitable for parallelization. We implemented it on Graphic Processing
Units (GPUs) and commodity CPUs. Its optimizations and differences from the F2
case are also analyzed.
We can solve 30+ quadratic equations in 30 variables on an NVIDIA GeForce GTX
980 Ti in 14 minutes; a cubic system takes 36 minutes. This well outperforms
existing solvers. Using these results, we compare Gröbner Bases vs. enumeration for
polynomial systems over small fields as the sizes go up.



## 2023/732

* Title: VerifMSI: Practical Verification of Hardware and Software Masking Schemes Implementations
* Authors: Quentin L. Meunier, Abdul Rahman Taleb
* [Permalink](https://eprint.iacr.org/2023/732)
* [Download](https://eprint.iacr.org/2023/732.pdf)

### Abstract

Side-Channel Attacks are powerful attacks which can recover secret information in a cryptographic device by analysing physical quantities such as power consumption. Masking is a common countermeasure to these attacks which can be applied in software and hardware, and consists in splitting the secrets in several parts. Masking schemes and their implementations are often not trivial, and require the use of automated tools to check for their correctness.
In this work, we propose a new practical tool named VerifMSI which extends an existing verification tool called LeakageVerif targeting software schemes. Compared to LeakageVerif, VerifMSI includes hardware constructs, namely gates and registers, what allows to take glitch propagation into account. Moreover, it includes a new representation of the inputs, making it possible to verify three existing security properties (Non-Interference, Strong Non-Interference, Probe Isolating Non-Interference) as well as a newly defined one called Relaxed Non-Interference, compared to the unique Threshold Probing Security verified in LeakageVerif. Finally, optimisations have been integrated in VerifMSI in order to speed up the verification.
We evaluate VerifMSI on a set of 9 benchmarks from the literature, focusing on the hardware descriptions, and show that it performs well both in terms of accuracy and scalability.



## 2023/733

* Title: On implemented graph based generator of cryptographically strong pseudorandom sequences of multivariate nature
* Authors: Vasyl Ustimenko, Tymoteusz Chojecki
* [Permalink](https://eprint.iacr.org/2023/733)
* [Download](https://eprint.iacr.org/2023/733.pdf)

### Abstract

Classical Multivariate Cryptography (MP) is searching for special families of functions of kind ^nF=T_1FTT_2 on the vector space V= (F_q)^n where F is a quadratic or cubical polynomial map of the space to itself, T_1 and T^2 are affine transformations and T is the piece of information such that the knowledge of the triple T_1, T_2, T allows the computation of reimage x of given nF(x) in polynomial time O(n^ᾳ). Traditionally F is given by the list of coefficients C(^nF) of its monomial terms ordered lexicographically. We consider the Inverse Problem of MP of finding T_1, T_2, T for F given in its standard form. The solution of inverse problem is harder than finding the procedure to compute the reimage of ^nF in time O(n^ᾳ). For general quadratic or cubic maps nF this is NP hard problem. In the case of special family some arguments on its inclusion to class NP has to be given.



## 2023/734

* Title: TLS → Post-Quantum TLS: Inspecting the TLS landscape for PQC adoption on Android
* Authors: Dimitri Mankowski, Thom Wiggers, Veelasha Moonsamy
* [Permalink](https://eprint.iacr.org/2023/734)
* [Download](https://eprint.iacr.org/2023/734.pdf)

### Abstract

The ubiquitous use of smartphones has contributed to more and more users conducting their online browsing activities through apps, rather than web browsers. In order to provide a seamless browsing experience to the users, apps rely on a variety of HTTP-based APIs and third-party libraries, and make use of the TLS protocol to secure the underlying communication. With NIST's recent announcement of the first standards for post-quantum algorithms, there is a need to better understand the constraints and requirements of TLS usage by Android apps in order to make an informed decision for migration to the post-quantum world.

In this paper, we performed an analysis of TLS usage by highest-ranked apps from Google Play Store to assess the resulting overhead for adoption of post-quantum algorithms. Our results show that apps set up large numbers of TLS connections with a median of 94, often to the same hosts. At the same time, many apps make little use of resumption to reduce the overhead of the TLS handshake. This will greatly magnify the impact of the transition to post-quantum cryptography, and we make recommendations for developers, server operators and the mobile operating systems to invest in making more use of these mitigating features or improving their accessibility. Finally, we briefly discuss how alternative proposals for post-quantum TLS handshakes might reduce the overhead.



## 2023/735

* Title: Privacy-preserving Attestation for Virtualized Network Infrastructures
* Authors: Ghada Arfaoui, Thibaut Jacques, Marc Lacoste, Cristina Onete, Léo Robert
* [Permalink](https://eprint.iacr.org/2023/735)
* [Download](https://eprint.iacr.org/2023/735.pdf)

### Abstract

In multi-tenant cloud environments, physical resources are shared between various parties (called tenants) through the use of virtual machines (VMs). Tenants can verify the state of their VMs by means of deep-attestation: a process by which a (physical or virtual) Trusted Platform Module --TPM -- generates attestation quotes about the integrity state of the VMs. Unfortunately, most existing deep-attestation solutions are either: limited to single-tenant environments, in which tenant {privacy is irrelevant; are inefficient in terms of {linking VM attestations to hypervisor attestations; or provide privacy and/or linking, but at the cost of modifying the TPM hardware.

In this paper, we propose a privacy preserving TPM-based deep-attestation solution in multi-tenant environments, which provably guarantees: (i) Inter-tenant privacy: a tenant is unaware of whether or not the physical machine hosting its VMs also contains other VMs (belonging to other tenants); (ii) Configuration privacy: the hypervisor's configuration, used in the attestation process, remains private with respect to the tenants requiring a hypervisor attestation; and (iii) Layer linking: our protocol enables tenants to link hypervisors with the VMs, thus obtaining a guarantee that their VMs are running on specific physical machines.

Our solution relies on vector commitments and ZK-SNARKs. We build on the security model of Arfaoui et al. and provide both formalizations of the properties we require and proofs that our scheme does, in fact attain them. Our protocol is scalable, and our implementation results prove that it is viable, even for a large number of VMs hosted on a single platform.



## 2023/736

* Title: Private Eyes: Zero-Leakage Iris Searchable Encryption
* Authors: Julie Ha, Chloe Cachet, Luke Demarest, Sohaib Ahmad, Benjamin Fuller
* [Permalink](https://eprint.iacr.org/2023/736)
* [Download](https://eprint.iacr.org/2023/736.pdf)

### Abstract

Biometric databases are being deployed with few cryptographic protections. Because of the nature of biometrics, privacy breaches affect users for their entire life.
This work introduces Private Eyes, the first zero-leakage biometric database. The only leakage of the system is unavoidable: 1) the log of the dataset size and 2) the fact that a query occurred. Private Eyes is built from symmetric searchable encryption. Proximity queries are the required functionality: given a noisy reading of a biometric, the goal is to retrieve all stored records that are close enough according to a distance metric.
Private Eyes combines locality sensitive-hashing or LSHs (Indyk and Motwani, STOC 1998) and encrypted maps. One searches for the disjunction of the LSHs of a noisy biometric reading. The underlying encrypted map needs to efficiently answer disjunction queries.
We focus on the iris biometric. Iris biometric data requires a large number of LSHs, approximately 1000. The most relevant prior work is in zero-leakage k-nearest-neighbor search (Boldyreva and Tang, PoPETS 2021), but that work is designed for a small number of LSHs.
Our main cryptographic tool is a zero-leakage disjunctive map designed for the setting when most clauses do not match any records. For the iris, on average at most 6% of LSHs match any stored value.
To aid in evaluation, we produce a synthetic iris generation tool to evaluate sizes beyond available iris datasets. This generation tool is a simple generative adversarial network. Accurate statistics are crucial to optimizing the cryptographic primitives so this tool may be of independent interest.
Our scheme is implemented and open-sourced. For the largest tested parameters of 5000 stored irises, search requires 26 rounds of communication and 26 minutes of single-threaded computation.



## 2023/737

* Title: Differential properties of integer multiplication
* Authors: Koustabh Ghosh, Joan Daemen
* [Permalink](https://eprint.iacr.org/2023/737)
* [Download](https://eprint.iacr.org/2023/737.pdf)

### Abstract

In this paper, we study the differential properties of integer multiplication between two $w$-bit integers, resulting in a $2w$-bit integer. Our objective is to gain insights into its resistance against differential cryptanalysis and asses its suitability as a source of non-linearity in symmetric key primitives.



## 2023/738

* Title: Extremal algebraic graphs, quadratic multivariate public keys and temporal rules
* Authors: Vasyl Ustimenko, Aneta Wróblewska
* [Permalink](https://eprint.iacr.org/2023/738)
* [Download](https://eprint.iacr.org/2023/738.pdf)

### Abstract

We introduce large groups of quadratic transformations of a vector space over the finite fields defined via symbolic computations with the usage of
algebraic constructions of Extremal Graph Theory. They can serve as platforms for the protocols of Noncommutative Cryptography with security based on the complexity of word decomposition problem in noncommutative polynomial transformation group.
The modifications of these symbolic computations in the case of large fields of characteristic two allow us to define quadratic bijective multivariate public keys such that the inverses of public maps has a large polynomial degree. Another family of public keys is defined over arbitrary commutative ring with unity.
We suggest the usage of constructed protocols for the private delivery of quadratic encryption maps instead of the public usage of these transformations, i.e. the idea of temporal multivariate rules with their periodical change.



## 2023/739

* Title: SMAUG: Pushing Lattice-based Key Encapsulation Mechanisms to the Limits
* Authors: Jung Hee Cheon, Hyeongmin Choe, Dongyeon Hong, MinJune Yi
* [Permalink](https://eprint.iacr.org/2023/739)
* [Download](https://eprint.iacr.org/2023/739.pdf)

### Abstract

Recently, NIST has announced Kyber, a lattice-based key encapsulation mechanism (KEM), as a post-quantum standard.
However, it is not the most efficient scheme among the NIST's KEM finalists.
Saber enjoys more compact sizes and faster performance, and Mera et al. (TCHES '21) further pushed its efficiency, proposing a shorter KEM, Sable.
As KEM are frequently used on the Internet, such as in TLS protocols, it is essential to achieve high efficiency while maintaining sufficient security.

In this paper, we further push the efficiency limit of lattice-based KEMs by proposing SMAUG, a new post-quantum KEM scheme submitted to the Korean Post-Quantum Cryptography (KPQC) competition, whose IND-CCA2 security is based on the combination of MLWE and MLWR problems.
We adopt several recent developments in lattice-based cryptography, targeting the textit{smallest} and the \textit{fastest} KEM while maintaining high enough security against various attacks, with a full-fledged use of sparse secrets.
Our design choices allow SMAUG to balance the decryption failure probability and ciphertext sizes without utilizing error correction codes, whose side-channel resistance remains open.

With a constant-time C reference implementation, SMAUG achieves ciphertext sizes up to 12% and 9% smaller than Kyber and Saber, with much faster running time, up to 103% and 58%, respectively.
Compared to Sable, SMAUG has the same ciphertext sizes but a larger public key, which gives a trade-off between the public key size versus performance; SMAUG has 39%-55% faster encapsulation and decapsulation speed in the parameter sets having comparable security.



## 2023/740

* Title: Practical Robust DKG Protocols for CSIDH
* Authors: Shahla Atapoor, Karim Baghery, Daniele Cozzo, Robi Pedersen
* [Permalink](https://eprint.iacr.org/2023/740)
* [Download](https://eprint.iacr.org/2023/740.pdf)

### Abstract

A Distributed Key Generation (DKG) protocol is an essential component of threshold cryptography. DKGs enable a group of parties to generate a secret and public key pair in a distributed manner so that the secret key is protected from being exposed, even if a certain number of parties are compromised. Robustness further guarantees that the construction of the key pair is always successful, even if malicious parties try to sabotage the computation. In this paper, we construct two efficient robust DKG protocols in the CSIDH setting that work with Shamir secret sharing. Both the proposed protocols are proven to be actively secure in the quantum random oracle model and use an Information Theoretically (IT) secure Verifiable Secret Sharing (VSS) scheme that is built using bivariate polynomials. As a tool, we construct a new piecewise verifiable proof system for structured public keys, that could be of independent interest. In terms of isogeny computations, our protocols outperform the previously proposed DKG protocols CSI-RAShi and Structured CSI-RAShi. As an instance, using our DKG protocols, 4 parties can sample a PK of size 4kB, for CSI-FiSh and CSI-SharK, respectively, 3.4 and 1.7 times faster than the current alternatives. On the other hand, since we use an IT-secure VSS, the fraction of corrupted parties is limited to less than a third and the communication cost of our schemes scales slightly worse with an increasing number of parties. For a low number of parties, our scheme still outperforms the alternatives in terms of communication.



## 2023/741

* Title: The Referendum Problem in Anonymous Voting for Decentralized Autonomous Organizations
* Authors: Artem Grigor, Vincenzo Iovino, Giuseppe Visconti
* [Permalink](https://eprint.iacr.org/2023/741)
* [Download](https://eprint.iacr.org/2023/741.pdf)

### Abstract

A natural approach to anonymous voting over Ethereum assumes that there is an off-chain aggregator that performs the following task. The aggregator receives valid signatures of YES/NO preferences from eligible voters and uses them to compute a zk-SNARK proof of the fact that the majority of voters have cast a preference for YES or NO. Then, the aggregator sends to the smart contract the zk-SNARK proof, the smart contract verifies the proof and can trigger an action (e.g., a transfer of funds). As the zk-SNARK proof guarantees anonymity, the privacy of the voters is preserved by attackers not colluding with the aggregator. Moreover, if the SNARK proof verification is efficient the GAS cost will be independent on the number of participating voters and signatures submitted by voters to the aggregator.
In this paper we show that this naive approach to run referenda over Ethereum can incur severe security problems. We propose both mitigations and hardness results for achieving voting procedures in which the proofs submitted on-chain are either ZK or succinct.



## 2023/742

* Title: Finding Desirable Substitution Box with SASQUATCH
* Authors: Manas Wadhwa, Anubhab Baksi, Kai Hu, Anupam Chattopadhyay, Takanori Isobe, Dhiman Saha
* [Permalink](https://eprint.iacr.org/2023/742)
* [Download](https://eprint.iacr.org/2023/742.pdf)

### Abstract

This paper presents ``SASQUATCH'', an open-source tool, that aids in finding an unknown substitution box (SBox) given its properties. The inspiration of our work can be directly attributed to the DCC 2022 paper by Lu, Mesnager, Cui, Fan and Wang. Taking their work as the foundation (i.e., converting the problem of SBox search to a satisfiability modulo theory instance and then invoking a solver), we extend in multiple directions (including -- but not limiting to -- coverage of more options, imposing time limit, parallel execution for multiple SBoxes, non-bijective SBox), and package everything within an easy-to-use interface. We also present ASIC benchmarks for some of the SBoxes.



## 2023/743

* Title: On Sustainable Ring-based Anonymous Systems
* Authors: Sherman S. M. Chow, Christoph Egger, Russell W. F. Lai, Viktoria Ronge, Ivy K. Y. Woo
* [Permalink](https://eprint.iacr.org/2023/743)
* [Download](https://eprint.iacr.org/2023/743.pdf)

### Abstract

Anonymous systems (e.g. anonymous cryptocurrencies and updatable anonymous credentials) often follow a construction template where an account can only perform a single anonymous action, which in turn potentially spawns new (and still single-use) accounts (e.g. UTXO with a balance to spend or session with a score to claim). Due to the anonymous nature of the action, no party can be sure which account has taken part in an action and, therefore, must maintain an ever-growing list of potentially unused accounts to ensure that the system keeps running correctly. Consequently, anonymous systems constructed based on this common template are seemingly not sustainable.

In this work, we study the sustainability of ring-based anonymous systems, where a user performing an anonymous action is hidden within a set of decoy users, traditionally called a ``ring''.

On the positive side, we propose a general technique for ring-based anonymous systems to achieve sustainability. Along the way, we define a general model of decentralised anonymous systems (DAS) for arbitrary anonymous actions, and provide a generic construction which provably achieves sustainability. As a special case, we obtain the first construction of anonymous cryptocurrencies achieving sustainability without compromising availability. We also demonstrate the generality of our model by constructing sustainable decentralised anonymous social networks.

On the negative side, we show empirically that Monero, one of the most popular anonymous cryptocurrencies, is unlikely to be sustainable without altering its current ring sampling strategy. The main subroutine is a sub-quadratic-time algorithm for detecting used accounts in a ring-based anonymous system.



## 2023/744

* Title: On Extremal Algebraic Graphs and implementations of new cubic Multivariate Public Keys
* Authors: Vasyl Ustimenko, Tymoteusz Chojecki, Michal Klisowski
* [Permalink](https://eprint.iacr.org/2023/744)
* [Download](https://eprint.iacr.org/2023/744.pdf)

### Abstract

Algebraic Constructions of Extremal Graph Theory
were efficiently used for the construction of Low Density Parity Check Codes for satellite communication, constructions of
stream ciphers and Postquantum Protocols of Noncommutative
cryptography and corresponding El Gamal type cryptosystems.
We shortly observe some results in these applications and present
idea of the usage of algebraic graphs for the development
of Multivariate Public Keys (MPK). Some MPK schemes are
presented at theoretical level, implementation of one of them is discussed.



## 2023/745

* Title: PSI from ring-OLE
* Authors: Wutichai Chongchitmate, Yuval Ishai, Steve Lu, Rafail Ostrovsky
* [Permalink](https://eprint.iacr.org/2023/745)
* [Download](https://eprint.iacr.org/2023/745.pdf)

### Abstract

Private set intersection (PSI) is one of the most extensively studied instances of secure computation. PSI allows two parties to compute the intersection of their input sets without revealing anything else. Other useful variants include PSI-Payload, where the output includes payloads associated with members of the intersection, and PSI-Sum, where the output includes the sum of the payloads instead of individual ones.

In this work, we make two related contributions. First, we construct simple and efficient protocols for PSI and PSI-Payload from a ring version of oblivious linear function evaluation (ring-OLE) that can be efficiently realized using recent ring-LPN based protocols. A standard OLE over a field F allows a sender with $a,b \in \mathbb{F}$ to deliver $ax+b$ to a receiver who holds $x \in \mathbb{F}$. Ring-OLE generalizes this to a ring $\mathcal{R}$, in particular, a polynomial ring over $\mathbb{F}$. Our second contribution is an efficient general reduction of a variant of PSI-Sum to PSI-Payload and secure inner product.

Our protocols have better communication cost than state-of-the-art PSI protocols, especially when requiring security against malicious parties and when allowing input-independent preprocessing. Compared to previous maliciously secure PSI protocols that have a similar com- putational cost, our online communication is 2x better for small sets (28 − 212 elements) and 20% better for large sets (220 − 224). Our protocol is also simpler to describe and implement. We obtain even bigger improvements over the state of the art (4-5x better running time) for our variant of PSI-Sum.



## 2023/746

* Title: Homomorphic Signatures for Subset and Superset Mixed Predicates and Its Applications
* Authors: Masahito Ishizaka, Kazuhide Fukushima
* [Permalink](https://eprint.iacr.org/2023/746)
* [Download](https://eprint.iacr.org/2023/746.pdf)

### Abstract

In homomorphic signatures for subset predicates (HSSB), each message (to be signed) is a set. Any signature on a set $M$ allows us to derive a signature on any subset $M'\subseteq M$. Its superset version, which should be called homomorphic signatures for superset predicates (HSSP), allows us to derive a signature on any superset $M'\supseteq M$. In this paper, we propose homomorphic signatures for subset and superset mixed predicates (HSSM) as a simple combination of HSSB and HSSP. In HSSM, any signature on a message of a set-pair $(M, W)$ allows us to derive a signature on any $(M', W')$ such that $M'\subseteq M$ and $W'\supseteq W$. We propose an original HSSM scheme which is unforgeable under the decisional linear assumption and completely context-hiding. We show that HSSM has various applications, which include disclosure-controllable HSSB, disclosure-controllable redactable signatures, (key-delegatable) superset/subset predicate signatures, and wildcarded identity-based signatures.



## 2023/747

* Title: Key-Range Attribute-Based Signatures for Range of Inner Product and Its Applications
* Authors: Masahito Ishizaka
* [Permalink](https://eprint.iacr.org/2023/747)
* [Download](https://eprint.iacr.org/2023/747.pdf)

### Abstract

In attribute-based signatures (ABS) for range of inner product (ARIP), recently proposed by Ishizaka and Fukushima at ICISC 2022, a secret-key labeled with an $n$-dimensional vector $\mathbf{x}\in\mathbb{Z}_p^n$ for a prime $p$ can used to sign a message under an $n$-dimensional vector $\mathbf{y}\in\mathbb{Z}_p^n$ and a range $[L,R]=\{L, L+1, \cdots, R-1, R\}$ with $L,R\in\mathbb{Z}_p$ iff their inner product is within the range, i.e., $\langle \mathbf{x}, \mathbf{y} \rangle \in [L,R]\pmod p$. We consider its key-range version, named key-range ARIP (KARIP), where the range $[L,R]$ is associated with a secret-key but not with a signature. We propose three generic KARIP constructions based on linearly homomorphic signatures and non-interactive witness-indistinguishable proof, which lead to concrete KARIP instantiations secure under standard assumptions with different features in terms of efficiency. We also show that KARIP has various applications, e.g., key-range ABS for range evaluation of polynomials/weighted averages/Hamming distance/Euclidean distance, key-range time-specific signatures, and key-range ABS for hyperellipsoid predicates.



## 2023/748

* Title: Towards the Links of Cryptanalytic Methods on MPC/FHE/ZK-Friendly Symmetric-Key Primitives
* Authors: Shiyao Chen, Chun Guo, Jian Guo, Li Liu, Meiqin Wang, Puwen Wei, Zeyu Xu
* [Permalink](https://eprint.iacr.org/2023/748)
* [Download](https://eprint.iacr.org/2023/748.pdf)

### Abstract

Symmetric-key primitives designed over the prime field $\mathbb{F}_p$ with odd characteristics, rather than the traditional $\mathbb{F}_2^{n}$, are becoming the most popular choice for MPC/FHE/ZK-protocols for better efficiencies. However, the security of $\mathbb{F}_p$ is less understood as there are highly nontrivial gaps when extending the cryptanalysis tools and experiences built on $\mathbb{F}_2^{n}$ in the past few decades to $\mathbb{F}_p$.

At CRYPTO 2015, Sun et al. established the links among impossible differential, zero-correlation linear, and integral cryptanalysis over $\mathbb{F}_2^{n}$ from the perspective of distinguishers. In this paper, following the definition of linear correlations over $\mathbb{F}_p$ by Baignéres, Stern and Vaudenay at SAC 2007, we successfully establish comprehensive links over $\mathbb{F}_p$, by reproducing the proofs and offering alternatives when necessary. Interesting and important differences between $\mathbb{F}_p$ and $\mathbb{F}_2^n$ are observed.

- Zero-correlation linear hulls can not lead to integral distinguishers for some cases over $\mathbb{F}_p$, while this is always possible over $\mathbb{F}_2^n$ proven by Sun et al..

- When the newly established links are applied to GMiMC, its impossible differential, zero-correlation linear hull and integral distinguishers can be increased by up to 3 rounds for most of the cases, and even to an arbitrary number of rounds for some special and limited cases, which only appeared in $\mathbb{F}_p$. It should be noted that all these distinguishers do not invalidate GMiMC's security claims.

The development of the theories over $\mathbb{F}_p$ behind these links, and properties identified (be it similar or different) will bring clearer and easier understanding of security of primitives in this emerging $\mathbb{F}_p$ field, which we believe will provide useful guides for future cryptanalysis and design.



## 2023/749

* Title: Note on Subversion-Resilient Key Exchange
* Authors: Magnus Ringerud
* [Permalink](https://eprint.iacr.org/2023/749)
* [Download](https://eprint.iacr.org/2023/749.pdf)

### Abstract

In this work, we set out to create a subversion resilient authenticated key exchange protocol. The first step was to design a meaningful security model for this primitive, and our goal was to avoid using building blocks like reverse firewalls and public watchdogs. We wanted to exclude these kinds of tools because we desired that our protocols to be self contained in the sense that we could prove security without relying on some outside, tamper-proof party. To define the model, we began by extending models for regular authenticated key exchange, as we wanted our model to retain all the properties from regular AKE.
While trying to design protocols that would be secure in this model, we discovered that security depended on more than just the protocol, but also on engineering questions like how keys are stored and accessed in memory. Moreover, even if we assume that we can find solutions to these engineering challenges, other problems arise when trying to develop a secure protocol, partly because it's hard to define what secure means in this setting.It is in particular not clear how a subverted algorithm should affect the freshness predicate inherited from trivial attacks in regular AKE. The attack variety is large, and it is not intuitive how one should treat or classify the different attacks.
In the end, we were unable to find a satisfying solution for our model, and hence we could not prove any meaningful security of the protocols we studied. This work is a summary of our attempt, and the challenges we faced before concluding it.



## 2023/750

* Title: BAKSHEESH: Similar Yet Different From GIFT
* Authors: Anubhab Baksi, Jakub Breier, Anupam Chattopadhyay, Tomáš Gerlich, Sylvain Guilley, Naina Gupta, Kai Hu, Takanori Isobe, Arpan Jati, Petr Jedlicka, Hyunjun Kim, Fukang Liu, Zdeněk Martinásek, Kosei Sakamoto, Hwajeong Seo, Rentaro Shiba, Ritu Ranjan Shrivastwa
* [Permalink](https://eprint.iacr.org/2023/750)
* [Download](https://eprint.iacr.org/2023/750.pdf)

### Abstract

We propose a lightweight block cipher named BAKSHEESH, which follows up on the popular cipher GIFT-128 (CHES'17). BAKSHEESH runs for 35 rounds, which is 12.50 percent smaller compared to GIFT-128 (runs for 40 rounds) while maintaining the same security claims against the classical attacks.

The crux of BAKSHEESH is to use a 4-bit SBox that has a non-trivial Linear Structure (LS). An SBox with one or more non-trivial LS has not been used in a cipher construction until DEFAULT (Asiacrypt'21). DEFAULT is pitched to have inherent protection against the Differential Fault Attack (DFA), thanks to its SBox having 3 non-trivial LS. BAKSHEESH, however, uses an SBox with only 1 non-trivial LS; and is a traditional cipher just like GIFT-128.

The SBox requires a low number of AND gates, making BAKSHEESH suitable for side channel countermeasures (when compared to GIFT-128) and other niche applications. Indeed, our study on the cost of the threshold implementation shows that BAKSHEESH offers a few-fold advantage over other lightweight ciphers. The design is not much deviated from its predecessor (GIFT-128), thereby allowing for easy implementation (such as fix-slicing in software). However, BAKSHEESH opts for the full-round key XOR, compared to the half-round key XOR in GIFT.

Thus, when taking everything into account, we show how a cipher construction can benefit from the unique vantage point of using 1 LS SBox, by combining the state-of-the-art progress in classical cryptanalysis and protection against device-dependent attacks. We, therefore, create a new paradigm of lightweight ciphers, by adequate deliberation on the design choice, and solidify it with appropriate security analysis and ample implementation/benchmark.



## 2023/751

* Title: Scalable Agreement Protocols with Optimal Optimistic Efficiency
* Authors: Yuval Gelles, Ilan Komargodski
* [Permalink](https://eprint.iacr.org/2023/751)
* [Download](https://eprint.iacr.org/2023/751.pdf)

### Abstract

Designing efficient distributed protocols for various agreement tasks such as Byzantine Agreement, Broadcast, and Committee Election is a fundamental problem. We are interested in $scalable$ protocols for these tasks, where each (honest) party communicates a number of bits which is sublinear in $n$, the number of parties. The first major step towards this goal is due to King et al. (SODA 2006) who showed a protocol where each party sends only $\tilde O(1)$ bits throughout $\tilde O(1)$ rounds, but guarantees only that $1-o(1)$ fraction of honest parties end up agreeing on a consistent output, assuming constant $<1/3$ fraction of static corruptions. Few years later, King et al. (ICDCN 2011) managed to get a full agreement protocol in the same model but where each party sends $\tilde O(\sqrt{n})$ bits throughout $\tilde O(1)$ rounds. Getting a full agreement protocol with $o(\sqrt{n})$ communication per party has been a major challenge ever since.

In light of this barrier, we propose a new framework for designing efficient agreement protocols. Specifically, we design $\tilde O(1)$-round protocols for all of the above tasks (assuming constant $<1/3$ fraction of static corruptions) with optimistic and pessimistic guarantees:

$\bullet$ $Optimistic$ $complexity$: In an honest execution, (honest) parties send only $\tilde O(1)$ bits.

$\bullet$ <i> xxx</i>$Pessimistic$ $complexity$: In any other case, (honest) parties send $\tilde O(\sqrt{n})$ bits.

Thus, all an adversary can gain from deviating from the honest execution is that honest parties will need to work harder (i.e., transmit more bits) to reach agreement and terminate. Besides the above agreement tasks, we also use our new framework to get a scalable secure multiparty computation (MPC) protocol with optimistic and pessimistic complexities.

Technically, we identify a relaxation of Byzantine Agreement (of independent interest) that allows us to fall-back to a pessimistic execution in a coordinated way by all parties. We implement this relaxation with $\tilde O(1)$ communication bits per party and within $\tilde O(1)$ rounds.



## 2023/752

* Title: Schnorr protocol in Jasmin
* Authors: Denis Firsov, Tiago Oliveira, Dominique Unruh
* [Permalink](https://eprint.iacr.org/2023/752)
* [Download](https://eprint.iacr.org/2023/752.pdf)

### Abstract

We implement the Schnorr proof system in assembler via the Jasmin toolchain, and prove the security (proof-of-knowledge property) and the absence of leakage through timing side-channels of that implementation in EasyCrypt.

In order to do so, we show how leakage-freeness of Jasmin programs can be proven for probabilistic programs (that are not constant-time). We implement and verify algorithms for fast constant-time modular multiplication and exponentiation (using Barrett reduction and Montgomery ladder). We implement and verify the rejection sampling algorithm. And finally, we put it all together and show the security of the overall implementation (end-to-end verification) of the Schnorr protocol, by connecting our implementation to prior security analyses in EasyCrypt (Firsov, Unruh, CSF 2023).



## 2023/753

* Title: A Faster Software Implementation of SQISign
* Authors: Kaizhan Lin, Weize Wang, Zheng Xu, Chang-An Zhao
* [Permalink](https://eprint.iacr.org/2023/753)
* [Download](https://eprint.iacr.org/2023/753.pdf)

### Abstract

Isogeny-based cryptography is famous for its short key size. As one of the most compact digital signatures, SQISign (Short Quaternion and Isogeny Signature) is attractive among post-quantum cryptography, but it is ineffcient compared to other post-quantum competitors because of complicated procedures in ideal to isogeny translation, which is the effciency bottleneck of the signing phase.
In this paper, we recall the current implementation of SQISign and
mainly discuss how to improve the execution of ideal to isogeny translation in SQISign. To be precise, we modify the SigningKLPT algorithm to accelerate the performance of generating the ideal $I_\sigma$. In addition, we explore how to save one of the two elliptic curve discrete logarithms and compute the remainder with the help of the reduced Tate pairing correctly and effciently. We speed up other procedures in ideal to isogeny translation with various techniques as well. It should be noted that our improvements also benefit the performances of key generation and verification in SQISign. In particular, in the instantiation with p3923 the improvements lead to a speedup of 8.82%, 8.50% and 18.94% for key generation, signature and verification, respectively



## 2023/754

* Title: Batch Proofs are Statistically Hiding
* Authors: Nir Bitansky, Chethan Kamath, Omer Paneth, Ron Rothblum, Prashant Nalini Vasudevan
* [Permalink](https://eprint.iacr.org/2023/754)
* [Download](https://eprint.iacr.org/2023/754.pdf)

### Abstract

Batch proofs are proof systems that convince a verifier that $x_1,\dots, x_t \in L$, for some $NP$ language $L$, with communication that is much shorter than sending the $t$ witnesses. In the case of statistical soundness (where the cheating prover is unbounded but honest prover is efficient), interactive batch proofs are known for $UP$, the class of unique witness $NP$ languages. In the case of computational soundness (aka arguments, where both honest and dishonest provers are efficient), non-interactive solutions are now known for all of $NP$, assuming standard cryptographic assumptions. We study the necessary conditions for the existence of batch proofs in these two settings. Our main results are as follows.

1. Statistical Soundness: the existence of a statistically-sound batch proof for $L$ implies that $L$ has a statistically witness indistinguishable ($SWI$) proof, with inverse polynomial $SWI$ error, and a non-uniform honest prover. The implication is unconditional for public-coin protocols and relies on one-way functions in the private-coin case.

This poses a barrier for achieving batch proofs beyond $UP$ (where witness indistinguishability is trivial). In particular, assuming that $NP$ does not have $SWI$ proofs, batch proofs for all of $NP$ do not exist. This motivates further study of the complexity class $SWI$, which, in contrast to the related class $SZK$, has been largely left unexplored.

2. Computational Soundness: the existence of batch arguments ($BARG$s) for $NP$, together with one-way functions, implies the existence of statistical zero-knowledge ($SZK$) arguments for $NP$ with roughly the same number of rounds, an inverse polynomial zero-knowledge error, and non-uniform honest prover.

Thus, constant-round interactive $BARG$s from one-way functions would yield constant-round $SZK$ arguments from one-way functions. This would be surprising as $SZK$ arguments are currently only known assuming constant-round statistically-hiding commitments (which in turn are unlikely to follow from one-way functions).

3. Non-interactive: the existence of non-interactive $BARG$s for $NP$ and one-way functions, implies non-interactive statistical zero-knowledge arguments ($NISZKA$) for $NP$, with negligible soundness error, inverse polynomial zero-knowledge error, and non-uniform honest prover. Assuming also lossy public-key encryption, the statistical zero-knowledge error can be made negligible. We further show that $BARG$s satisfying a notion of honest somewhere extractability imply lossy public key encryption.

All of our results stem from a common framework showing how to transform a batch protocol for a language $L$ into an $SWI$ protocol for $L$.



## 2023/755

* Title: The security of Kyber's FO-transform
* Authors: Manuel Barbosa, Andreas Hülsing
* [Permalink](https://eprint.iacr.org/2023/755)
* [Download](https://eprint.iacr.org/2023/755.pdf)

### Abstract

In this short note we give another direct proof for the variant of the FO transform used by Kyber in the QROM. At PKC'23 Maram & Xagawa gave the first direct proof which does not require the indirection via FO with explicit rejection, thereby avoiding either a non-tight bound, or the necessity to analyze the failure probability in a new setting. However, on the downside their proof produces a bound that incurs an additive collision bound term. We explore a different approach for a direct proof, which results in a simpler argument closer to prior proofs, but a slightly worse bound.



## 2023/756

* Title: SDitH in the QROM
* Authors: Carlos Aguilar-Melchor, Andreas Hülsing, David Joseph, Christian Majenz, Eyal Ronen, Dongze Yue
* [Permalink](https://eprint.iacr.org/2023/756)
* [Download](https://eprint.iacr.org/2023/756.pdf)

### Abstract

The MPC in the Head (MPCitH) paradigm has recently led to significant improvements for signatures in the code-based setting. In this paper we consider some modifications to a recent twist of MPCitH, called Hypercube-MPCitH, that in the code-based setting provides the currently best known signature sizes. By compressing the Hypercube-MPCitH five round code-based identification into three rounds we obtain two main benefits. On the one hand, it allows us to further
develop recent techniques to provide a tight security proof in the quantum-accessible random oracle model (QROM), avoiding the catastrophic reduction losses incurred using generic QROM-results
for Fiat-Shamir. On the other hand, we can reduce the already low-cost online part of the signature to just a hash and some serialization. In addition, we propose the introduction of proof-of-work techniques to allow for a reduction in signature size. On the technical side, we develop generalizations of several QROM proof techniques and introduce a variant of the recently proposed extractable QROM.