## In this issue

1. [2024/556] Menhir: An Oblivious Database with Protection ...
2. [2024/557] Permutation-Based Hash Chains with Application to ...
3. [2024/769] Time-Based Cryptography From Weaker Assumptions: ...
4. [2024/776] Instance-Hiding Interactive Proofs
5. [2024/777] Measure-Rewind-Extract: Tighter Proofs of One-Way ...
6. [2024/778] Ideal-to-isogeny algorithm using 2-dimensional ...
7. [2024/779] Elliptic Curve Cryptography for the masses: Simple ...
8. [2024/780] Information-theoretic Multi-server Private ...
9. [2024/781] Doubly-Efficient Batch Verification in Statistical ...
10. [2024/782] Relating Code Equivalence to Other Isomorphism Problems
11. [2024/783] Differential Cryptanalysis on Quantum Computers
12. [2024/784] Universal Blockchain Assets
13. [2024/785] SmartBean: Transparent, Concretely Efficient, ...
14. [2024/786] Modelling Ciphers with Overdefined Systems of ...
15. [2024/787] A new attack against search-LWE using Diophantine ...
16. [2024/788] A Fault-Resistant NTT by Polynomial Evaluation and ...
17. [2024/789] FairSec: Fair and Maliciously Secure Circuit-PSI ...
18. [2024/790] Physical Ring Signature
19. [2024/791] Minimize the Randomness in Rasta-Like Designs: How ...
20. [2024/792] Stickel's Key Agreement Algebraic Variation
21. [2024/793] Hide-and-Seek and the Non-Resignability of the BUFF ...
22. [2024/794] Detecting Rogue Decryption in (Threshold) ...
23. [2024/795] New Limits of Provable Security and Applications to ...
24. [2024/796] Weak Consistency mode in Key Transparency: OPTIKS
25. [2024/797] Nonadaptive One-Way to Hiding Implies Adaptive ...
26. [2024/798] Incompressible Functional Encryption
27. [2024/799] Symmetric Signcryption and E2EE Group Messaging in ...
28. [2024/800] A Note on Zero-Knowledge for NP and One-Way Functions
29. [2024/801] Algebraic Structure of the Iterates of $\chi$
30. [2024/802] On Maximum Size Simultaneous Linear Approximations ...
31. [2024/803] Can We Beat Three Halves Lower Bound?: ...
32. [2024/804] Analysis on Sliced Garbling via Algebraic Approach
33. [2024/805] DiTRU: A Resurrection of NTRU over Dihedral Group
34. [2024/806] Resettable Statistical Zero-Knowledge for NP
35. [2024/807] Optimal Consensus in the Presence of Overlapping ...
36. [2024/808] Arma: Byzantine Fault Tolerant Consensus with ...
37. [2024/809] Reducing Overdefined Systems of Polynomial ...
38. [2024/810] The Perils of Limited Key Reuse: Adaptive and ...
39. [2024/811] Traceable Secret Sharing Based on the Chinese ...
40. [2024/812] Relations among new CCA security notions for ...
41. [2024/813] How to Redact the Bitcoin Backbone Protocol
42. [2024/814] Succinct Homomorphic Secret Sharing
43. [2024/815] Faster verifications and smaller signatures: Trade- ...
44. [2024/816] Zero-knowledge IOPs Approaching Witness Length
45. [2024/817] DVA: Dangerous Variations of ALTEQ
46. [2024/818] The Brave New World of Global Generic Groups and ...
47. [2024/819] A new stand-alone MAC construct called SMAC
48. [2024/820] Rate-1 Arithmetic Garbling from Homomorphic Secret- ...
49. [2024/821] A General Framework for Lattice-Based ABE Using ...
50. [2024/822] Early Stopping Byzantine Agreement in ...
51. [2024/823] Batched Distributed Point Function from Sparse LPN ...
52. [2024/824] Improved Meet-LWE Attack via Ternary Trees

## 2024/556

* Title: Menhir: An Oblivious Database with Protection against Access and Volume Pattern Leakage
* Authors: Leonie Reichert, Gowri R Chandran, Phillipp Schoppmann, Thomas Schneider, Björn Scheuermann
* [Permalink](https://eprint.iacr.org/2024/556)
* [Download](https://eprint.iacr.org/2024/556.pdf)

### Abstract

Analyzing user data while protecting the privacy of individuals remains a big challenge. Trusted execution environments (TEEs) are a possible solution as they protect processes and Virtual Machines (VMs) against malicious hosts. However, TEEs can leak
access patterns to code and to the data being processed. Furthermore, when data is stored in a TEE database, the data volume required to answer a query is another unwanted side channel that contains sensitive information. Both types of information leaks,
access patterns and volume patterns, allow for database reconstruction attacks.

In this paper, we present Menhir, an oblivious TEE database that hides access patterns with ORAM guarantees and volume patterns through differential privacy. The database allows range and point queries with SQL-like WHERE-clauses. It builds on the state-
of-the-art oblivious AVL tree construction Oblix (S&P'18), which by itself does not protect against volume leakage. We show how volume leakage can be exploited in range queries and improve the construction to mitigate this type of attack. We prove the
correctness and obliviousness of Menhir. Our evaluation shows that our approach is feasible and scales well with the number of rows and columns in the database.



## 2024/557

* Title: Permutation-Based Hash Chains with Application to Password Hashing
* Authors: Charlotte Lefevre, Bart Mennink
* [Permalink](https://eprint.iacr.org/2024/557)
* [Download](https://eprint.iacr.org/2024/557.pdf)

### Abstract

Hash chain based password systems are a useful way to guarantee authentication with one-time passwords. The core idea is specified in RFC 1760 as S/Key. At CCS 2017, Kogan et al. introduced T/Key, an improved password system where one-time passwords are
only valid for a limited time period. They proved security of their construction in the random oracle model under a basic modeling of the adversary. In this work, we make various advances in the analysis and instantiation of hash chain based password
systems. Firstly, we describe a slight generalization called U/Key that allows for more flexibility in the instantiation and analysis, and we develop a security model that refines the adversarial strength into offline and online complexity, that can be
used beyond the random oracle model, and that allows to argue multi-user security directly. Secondly, we derive a new security proof of U/Key in the random oracle model, as well as dedicated and tighter security proofs of U/Key instantiated with a sponge
construction and a truncated permutation. These dedicated security proofs, in turn, solve a problem of understanding the preimage resistance of a cascaded evaluation of the sponge construction. When applied to T/Key, these results improve significantly
over the earlier results: whereas the originally suggested instantiation using SHA-256 uses a compression function that maps 768 bits into 256 bits, with a truncated permutation construction one can generically achieve 128 bits of security already with
a permutation of size 256 bits.



## 2024/769

* Title: Time-Based Cryptography From Weaker Assumptions: Randomness Beacons, Delay Functions and More
* Authors: Damiano Abram, Lawrence Roy, Mark Simkin
* [Permalink](https://eprint.iacr.org/2024/769)
* [Download](https://eprint.iacr.org/2024/769.pdf)

### Abstract

The assumption that certain computations inherently require some sequential time has established itself as a powerful tool for cryptography. It allows for security and liveness guarantees in distributed protocols that are impossible to achieve with
classical hardness assumptions. Unfortunately, many constructions from the realm of time-based cryptography are based on new and poorly understood hardness assumptions, which tend not to stand the test of time (cf. Leurent et al. 2023, Peikert & Tang
2023).
In this work, we make progress on several fronts. We formally define the concept of a delay function and present a construction thereof from minimal assumptions. We show that these functions, in combination with classical cryptographic objects that
satisfy certain efficiency criteria, would allow for constructing delay encryption, which is otherwise only known to exist based on a new hardness assumption about isogenies. We formally define randomness beacons as they are used in the context of
blockchains, and we show that (linearly homomorphic) time-lock puzzles allow for efficiently constructing them.
Our work puts time-based cryptography on a firmer theoretical footing, provides new constructions from simpler assumptions, and opens new avenues for constructing delay encryption.



## 2024/776

* Title: Instance-Hiding Interactive Proofs
* Authors: Changrui Mu, Prashant Nalini Vasudevan
* [Permalink](https://eprint.iacr.org/2024/776)
* [Download](https://eprint.iacr.org/2024/776.pdf)

### Abstract

In an Instance-Hiding Interactive Proof (IHIP) [Beaver et al. CRYPTO 90], an efficient verifier with a _private_ input x interacts with an unbounded prover to determine whether x is contained in a language L. In addition to completeness and soundness,
the instance-hiding property requires that the prover should not learn anything about x in the course of the interaction. Such proof systems capture natural privacy properties, and may be seen as a generalization of the influential concept of Randomized
Encodings [Ishai et al. FOCS 00, Applebaum et al. FOCS 04, Agrawal et al. ICALP 15], and as a counterpart to Zero-Knowledge proofs [Goldwasser et al. STOC 89].

We investigate the properties and power of such instance-hiding proofs, and show the following:
1. Any language with an IHIP is contained in AM/poly and coAM/poly.
2. If an average-case hard language has an IHIP, then One-Way Functions exist.
3. There is an oracle with respect to which there is a language that has an IHIP but not an SZK proof.
4. IHIP's are closed under composition with any efficiently computable function.

We further study a stronger version of IHIP (that we call Strong IHIP) where the view of the honest prover can be efficiently simulated. For these, we obtain stronger versions of some of the above:
5. Any language with a Strong IHIP is contained in AM and coAM.
6. If a _worst-case_ hard language has a Strong IHIP, then One-Way Functions exist.



## 2024/777

* Title: Measure-Rewind-Extract: Tighter Proofs of One-Way to Hiding and CCA Security in the Quantum Random Oracle Model
* Authors: Jiangxia Ge, Heming Liao, Rui Xue
* [Permalink](https://eprint.iacr.org/2024/777)
* [Download](https://eprint.iacr.org/2024/777.pdf)

### Abstract

The One-Way to Hiding (O2H) theorem, first given by Unruh (J ACM 2015) and then restated by Ambainis et al. (CRYPTO 2019), is a crucial technique for solving the reprogramming problem in the quantum random oracle model (QROM). It provides an upper bound $
d\cdot\sqrt{\epsilon}$ for the distinguisher's advantage, where $d$ is the query depth and $\epsilon$ denotes the advantage of a one-wayness attacker. Later, in order to obtain a tighter upper bound, Kuchta et al. (EUROCRYPT 2020) proposed the Measure-
Rewind-Measure (MRM) technique and then proved the Measure-Rewind-Measure O2H (MRM-O2H) theorem, which provides the upper bound $d\cdot\epsilon$. They also proposed an open question: Can we combine their MRM technique with Ambainis et al.'s semi-
classical oracle technique (CRYPTO 2019) or Zhandry's compressed oracle technique (CRYPTO 2019) to prove a new O2H theorem with an upper bound even tighter than $d\cdot\epsilon$?

In this paper, we give an affirmative answer for the above question. We propose a new technique named Measure-Rewind-Extract (MRE) by combining the MRM technique with the semi-classical oracle technique. By using MRE technique, we prove the Measure-
Rewind-Extract O2H (MRE-O2H) theorem, which provides the upper bound $\sqrt{d}\cdot\epsilon$.

As an important application of our MRE-O2H theorem, for the $FO^{\cancel{\bot}}$, $FO_m^{\cancel{\bot}}$, $FO^{\bot}$ and $FO_m^\bot$ proposed by Hofheinz et al. (TCC 2017), i.e., the key encapsulation mechanism (KEM) variants of the Fujisaki-Okamoto
transformation, we prove the following results in the QROM:

Their IND-CCA security can be reduced to the IND-CPA security of the underlying public key encryption (PKE) scheme without the square-root advantage loss. In particular, compared with the IND-CCA proof of $FO^{\cancel{\bot}}$ given by Kuchta et al. (
EUROCRYPT 2020), ours removes the injectivity assumption and has a tighter security bound.

Under the assumption that the underlying PKE scheme is unique randomness recoverable, we for the first time prove that their IND-CCA security can be reduced to the OW-CPA security of the underlying PKE scheme without the square-root advantage loss.



## 2024/778

* Title: Ideal-to-isogeny algorithm using 2-dimensional isogenies and its application to SQIsign
* Authors: Hiroshi Onuki, Kohei Nakagawa
* [Permalink](https://eprint.iacr.org/2024/778)
* [Download](https://eprint.iacr.org/2024/778.pdf)

### Abstract

The Deuring correspondence is a correspondence between supersingular elliptic curves and quaternion orders. Under this correspondence, an isogeny between elliptic curves corresponds to a quaternion ideal. This correspondence plays an important role in
isogeny-based cryptography and several algorithms to compute an isogeny corresponding to a quaternion ideal (ideal-to-isogeny algorithms) have been proposed. In particular, SQIsign is a signature scheme based on the Deuring correspondence and uses an
ideal-to-isogeny algorithm. In this paper, we propose a novel ideal-to-isogeny algorithm using isogenies of dimension $2$. Our algorithm is based on Kani's reducibility theorem, which gives a connection between isogenies of dimension $1$ and $2$. By
using the characteristic $p$ of the base field of the form $2^fg - 1$ for a small odd integer $g$, our algorithm works by only $2$-isogenies and $(2, 2)$-isogenies in the operations in $\mathbb{F}_{p^2}$. We apply our algorithm to SQIsign and compare the
efficiency of the new algorithm with the existing one. Our analysis shows that the key generation and the signing in our algorithm are at least twice as fast as those in the existing algorithm at the NIST security level 1. This advantage becomes more
significant at higher security levels. In addition, our algorithm also improves the efficiency of the verification in SQIsign.



## 2024/779

* Title: Elliptic Curve Cryptography for the masses: Simple and fast finite field arithmetic
* Authors: Michael Scott
* [Permalink](https://eprint.iacr.org/2024/779)
* [Download](https://eprint.iacr.org/2024/779.pdf)

### Abstract

Shaped prime moduli are often considered for use in elliptic curve and isogeny-based cryptography to allow for faster modular reduction. Here we focus on the most common choices for shaped primes that have been suggested, that is pseudo-Mersenne,
generalized Mersenne and Montgomery-friendly primes. We consider how best to to exploit these shapes for maximum efficiency, and provide an open source tool to automatically generate, test and time working high-level language finite-field code. Next we
consider the advantage to be gained from implementations that are written in assembly language and which exploit special instructions, SIMD hardware if present, and the particularities of the algorithm being implemented.



## 2024/780

* Title: Information-theoretic Multi-server Private Information Retrieval with Client Preprocessing
* Authors: Jaspal Singh, Yu Wei, Vassilis Zikas
* [Permalink](https://eprint.iacr.org/2024/780)
* [Download](https://eprint.iacr.org/2024/780.pdf)

### Abstract

A private information retrieval (PIR) protocol allows a client to fetch any entry from single or multiple servers who hold a public database (of size $n$) while ensuring no server learns any information about the client's query. Initial works on PIR were
focused on reducing the communication complexity of PIR schemes. However, standard PIR protocols are often impractical to use in applications involving large databases, due to its inherent large server-side computation complexity, that's at least linear
in the database size. Hence, a line of research has focused on considering alternative PIR models that can achieve improved server complexity.

The model of private information retrieval with client prepossessing has received a lot of interest beginning with the work due to Corrigan-Gibbs and Kogan (Eurocrypt 2020). In this model, the client interacts with two servers in an offline phase and
it stores a local state, which it uses in the online phase to perform PIR queries. Constructions in this model achieve online client/server computation and bandwidth that's sublinear in the database size, at the cost of a one-time expensive offline phase.
Till date all known constructions in this model are based on symmetric key primitives or on stronger public key assumptions like Decisional Diffie-Hellman (DDH) and Learning with Error (LWE). This work initiates the study of unconditional PIR with
client prepossessing - where we avoid using any cryptographic assumptions. We present a new PIR protocol for $2t$ servers (where $t \in [2,\log_2n/2]$) with threshold 1, where client and server online computation is $\widetilde{O}(\sqrt{n})$ (the $\
widetilde{O}(.)$ notation hides $\textsf{poly}\log$ factors) - matching the computation costs of other works based on cryptographic assumptions. The client storage and online communication complexity are $\widetilde{O}(n^{0.5+1/2t})$ and $\widetilde{O}(
n^{1/2})$ respectively. Compared to previous works our PIR with client preprocessing protocol also has a very concretely efficient client/server online computation phase - which is dominated by xor operations, compared to cryptographic operations that
are orders of magnitude slower. As a building block for our construction, we introduce a new information-theoretic primitive called \textit{privately multi-puncturable random set }(\pprs), which might be of independent interest. This new primitive can
be viewed as as a generalization of privately puncturable pseudo-random set, which is the key cryptographic building block used in previous works on PIR with client preprocessing.



## 2024/781

* Title: Doubly-Efficient Batch Verification in Statistical Zero-Knowledge
* Authors: Or Keret, Ron D. Rothblum, Prashant Nalini Vasudevan
* [Permalink](https://eprint.iacr.org/2024/781)
* [Download](https://eprint.iacr.org/2024/781.pdf)

### Abstract

A sequence of recent works, concluding with Mu et al. (Eurocrypt, 2024) has shown that every problem $\Pi$ admitting a non-interactive statistical zero-knowledge proof (NISZK) has an efficient zero-knowledge batch verification protocol. Namely, an NISZK
protocol for proving that $x_1,\dots,x_k \in \Pi$ with communication that only scales poly-logarithmically with $k$. A caveat of this line of work is that the prover runs in exponential-time, whereas for NP problems it is natural to hope to obtain a
doubly-efficient proof - that is, a prover that runs in polynomial-time given the $k$ NP witnesses.

In this work we show that every problem in $NISZK \cap UP$ has a doubly-efficient interactive statistical zero-knowledge proof with communication $poly(n,\log(k))$ and $poly(\log(k),\log(n))$ rounds. The prover runs in time $poly(n,k)$ given access
to the $k$ UP witnesses. Here $n$ denotes the length of each individual input, and UP is the subclass of NP relations in which YES instances have unique witnesses.

This result yields doubly-efficient statistical zero-knowledge batch verification protocols for a variety of concrete and central cryptographic problems from the literature.



## 2024/782

* Title: Relating Code Equivalence to Other Isomorphism Problems
* Authors: Huck Bennett, Kaung Myat Htay Win
* [Permalink](https://eprint.iacr.org/2024/782)
* [Download](https://eprint.iacr.org/2024/782.pdf)

### Abstract

We study the complexity of the Code Equivalence Problem on linear error-correcting codes by relating its variants to isomorphism problems on other discrete structures---graphs, lattices, and matroids. Our main results are a fine-grained reduction from
the Graph Isomorphism Problem to the Linear Code Equivalence Problem over any field $\mathbb{F}$, and a reduction from the Linear Code Equivalence Problem over any field $\mathbb{F}_p$ of prime, polynomially bounded order $p$ to the Lattice Isomorphism
Problem. Both of these reductions are simple and natural. We also give reductions between variants of the Code Equivalence Problem, and study the relationship between isomorphism problems on codes and linear matroids.



## 2024/783

* Title: Differential Cryptanalysis on Quantum Computers
* Authors: Kyungbae Jang, Yujin Oh, Hwajeong Seo
* [Permalink](https://eprint.iacr.org/2024/783)
* [Download](https://eprint.iacr.org/2024/783.pdf)

### Abstract

As quantum computing progresses, extensive research has been conducted to find quantum advantages in the field of cryptography. Combining quantum algorithms with classical cryptographic analysis methods, such as differential cryptanalysis and linear
cryptanalysis, has the potential to reduce complexity.

In this paper, we present a quantum differential finding circuit for differential cryptanalysis. In our quantum circuit, both plaintext and input difference are in a superposition state. Actually, while our method cannot achieve a direct speedup with
quantum computing, it offers a different perspective by relying on quantum probability in a superposition state.

For the quantum simulation, given the limited number of qubits, we simulate our quantum circuit by implementing the Toy-ASCON quantum circuit.



## 2024/784

* Title: Universal Blockchain Assets
* Authors: Owen Vaughan
* [Permalink](https://eprint.iacr.org/2024/784)
* [Download](https://eprint.iacr.org/2024/784.pdf)

### Abstract

We present a novel protocol for issuing and transferring tokens across blockchains without the need of a trusted third party or cross-chain bridge. In our scheme, the blockchain is used for double-spend protection only, while the authorisation of token
transfers is performed off-chain. Due to the universality of our approach, it works in almost all blockchain settings. It can be implemented immediately on UTXO blockchains such as Bitcoin without modification, and on account-based blockchains such as
Ethereum by introducing a smart contract that mimics the properties of a UTXO. We provide a proof-of-concept implementation of an NFT that is issued on Bitcoin, transferred to Ethereum, and then transferred back to Bitcoin. Our new approach means that
users no longer need to be locked into one blockchain when issuing and transferring tokens.



## 2024/785

* Title: SmartBean: Transparent, Concretely Efficient, Polynomial Commitment Scheme with Logarithmic Verification and Communication Costs that Runs on Any Group
* Authors: Frank Y.C. Lu
* [Permalink](https://eprint.iacr.org/2024/785)
* [Download](https://eprint.iacr.org/2024/785.pdf)

### Abstract

We introduce a new, concretely efficient, transparent polynomial commitment scheme with logarithmic verification time and communication cost that can run on any group. Existing group-based polynomial commitment schemes must use less efficient groups,
such as class groups of unknown order or pairing-based groups to achieve transparency (no trusted setup), making them expensive to adopt in practice. 

We offer the first group-based polynomial commitment scheme that can run on any group s.t. it does not rely on expensive pairing operations or require class groups of unknown order to achieve transparency while still providing logarithmic verifier time
and communication cost. 

The prover work of our work is dominated by $4n \,\mathbb{G}$ multi-exponentiations, the verifier work is dominated by 4 log $n \, \mathbb{G}$ exponentiations, and the communication cost is 4 log $n \, \mathbb{G}$. Since our protocol can run on fast
groups such as Curve25519, we can easily accelerate the multi-exponentiations with Pippenger's algorithm. The concrete performance of our work shows a significant improvement over the current state of the art in almost every aspect.



## 2024/786

* Title: Modelling Ciphers with Overdefined Systems of Quadratic Equations: Application to Friday, Vision, RAIN and Biscuit
* Authors: Fukang Liu, Mohammad Mahzoun, Willi Meier
* [Permalink](https://eprint.iacr.org/2024/786)
* [Download](https://eprint.iacr.org/2024/786.pdf)

### Abstract

It is well-known that a system of equations becomes easier to solve when it is overdefined. In this work, we study how to overdefine the system of equations to describe the arithmetic oriented (AO) ciphers Friday, Vision, and RAIN, as well as a special
system of quadratic equations over $\mathbb F_{2^{\ell}}$ used in the post-quantum signature scheme Biscuit. Our method is inspired by Courtois-Pieprzyk's and Murphy-Robshaw's methods to model AES with overdefined systems of quadratic equations over $\
mathbb F_2$ and $\mathbb F_{2^8}$, respectively. However, our method is more refined and much simplified compared with Murphy-Robshaw's method, since it can take full advantage of the low-degree $\mathbb F_2$-linearized affine polynomials used in Friday
and Vision, and the overdefined system of equations over $\mathbb F_{2^{\ell}}$ can be described in a clean way with our method. For RAIN, we instead consider quadratic Boolean equations rather than equations over large finite fields $\mathbb F_{2^{\ell}}
$. Specifically, we demonstrate that the special structure of RAIN allows us to set up much more linearly independent quadratic Boolean equations than those obtained only with Courtois-Pieprzyk's method. Moreover, we further demonstrate that the
underlying key-recovery problem in Biscuit (NIST PQC Round 1 Additional Signatures) can also be described by solving a much overdefined system of quadratic equations over $\mathbb F_{2^{\ell}}$. On the downside, the constructed systems of quadratic
equations for these ciphers cannot be viewed as semi-regular, which makes it challenging to upper bound the complexity of the Gröbner basis attack. However, such a new modelling method can significantly improve the lower bound of the complexity of the
Gröbner basis attacks on these ciphers, i.e., we view the complexity of solving a random system of quadratic equations of the same scale as the lower bound. How to better estimate the upper and lower bounds of the Gröbner basis attacks on these ciphers
based on our modelling method is left as an open problem.



## 2024/787

* Title: A new attack against search-LWE using Diophantine approximations
* Authors: Robin Frot, Daniel Zentai
* [Permalink](https://eprint.iacr.org/2024/787)
* [Download](https://eprint.iacr.org/2024/787.pdf)

### Abstract

In this paper, we present a new attack against search-LWE instances with a small secret key. The method consists of lifting the public key to $\mathbb Z$ and finding a good Diophantine approximation of the public key divided by the modulus $a$. This is
done using lattice reduction algorithms. The lattice considered, and the approximation quality needed is similar to known decision-LWE attacks for small keys. However, we do not require an in-depth analysis of the reduction algorithm (any reduction
algorithm giving small enough vectors is enough for us), and our method solves the search problem directly, which is harder than the decision problem.



## 2024/788

* Title: A Fault-Resistant NTT by Polynomial Evaluation and Interpolation
* Authors: Sven Bauer, Fabrizio De Santis, Kristjane Koleci, Anita Aghaie
* [Permalink](https://eprint.iacr.org/2024/788)
* [Download](https://eprint.iacr.org/2024/788.pdf)

### Abstract

In computer arithmetic operations, the Number Theoretic
Transform (NTT) plays a significant role in the efficient implementation
of cyclic and nega-cyclic convolutions with the application of multiplying large integers and large degree polynomials. Multiplying polynomials is
a common operation in lattice-based cryptography. Hence, the NTT is a
core component of several lattice-based cryptographic algorithms. Two well-known examples are the key encapsulation mechanism Kyber and
the digital signature algorithm Dilithium. In this work, we introduce a
novel and efficient method for safeguarding the NTT against fault attacks.
This new countermeasure is based on polynomial evaluation and
interpolation. We prove its error detection capability, calculate the required additional computational effort, and show how to concretely use
it to secure the NTT in Kyber and Dilithium against fault injection
attacks. Finally, we provide concrete implementation results of the proposed novel technique on a resource-constrained ARM Cortex-M4 microcontroller,
e.g., the technique exhibits a 72% relative overhead, when
applied to Dilithium.



## 2024/789

* Title: FairSec: Fair and Maliciously Secure Circuit-PSI via SPDZ-Compatible Oblivious PRF
* Authors: Yaxi Yang, Xiaojian Liang, Xiangfu Song, Linting Huang, Hongyu Ren, Changyu Dong, Jianying Zhou
* [Permalink](https://eprint.iacr.org/2024/789)
* [Download](https://eprint.iacr.org/2024/789.pdf)

### Abstract

Private Set Intersection (PSI) allows two parties to compute the intersection of their input sets without revealing more information than the computation results. PSI and its variants have numerous applications in practice. Circuit-PSI is a famous
variant and aims to compute any functionality $f$ on items in the intersection set. However, the existing circuit-PSI protocols only provide security against \emph{semi-honest} adversaries. One straightforward solution is to extend a pure garbled-circuit-
based PSI (NDSS'12) to a maliciously secure circuit-PSI, but it will result in non-concrete complexity. Another is converting state-of-the-art semi-honest circuit-PSI protocols (EUROCRYPT'21; PoPETS'22) to be secure in the malicious setting. However, it
will come across \emph{the consistency issue} since parties can not guarantee the inputs of functionality $f$ stay unchanged as obtained from the last step.

This paper addresses the aforementioned issue by introducing FairSec, the first malicious circuit-PSI protocol. The central building block of FairSec, called Distributed Dual-key Oblivious PRF (DDOPRF), provides an oblivious evaluation of secret-shared
inputs with dual keys. Additionally, we ensure the compatibility of DDOPRF with SPDZ, enhancing the versatility of our circuit-PSI protocol. Notably, our construction allows us to guarantee fairness within circuit-PSI effortlessly. Importantly, FairSec
also achieves linear computation and communication complexities.



## 2024/790

* Title: Physical Ring Signature
* Authors: Xavier Bultel
* [Permalink](https://eprint.iacr.org/2024/790)
* [Download](https://eprint.iacr.org/2024/790.pdf)

### Abstract

Ring signatures allow members of a group (called "ring") to sign a message anonymously within the group, which is chosen ad hoc at the time of signing (the members do not need to have interacted before). In this paper, we propose a physical version of
ring signatures. Our signature is based on one-out-of-many signatures, a method used in many real cryptographic ring signatures. It consists of boxes containing coins locked with padlocks that can only be opened by a particular group member. To sign a
message, a group member shakes the boxes of the other members of the group so that the coins are in a random state ("heads" or "tails", corresponding to bits $0$ and $1$), and opens their box to arrange the coins so that the exclusive "or" of the coins
corresponds to the bits of the message they wish to sign. We present a prototype that can be used with coins, or with dice for messages encoded in larger (non-binary) alphabets. We suggest that this system can be used to explain ring signatures to the
general public in a fun way. Finally, we propose a semi-formal analysis of the security of our signature based on real cryptographic security proofs.



## 2024/791

* Title: Minimize the Randomness in Rasta-Like Designs: How Far Can We Go?

[continued in next message]

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