[digest] 2022 Week 37

[IACR ePrint Archive]

## In this issue

1. [2022/1192] (Augmented) Broadcast Encryption from Identity ...
2. [2022/1193] Knowledge Encryption and Its Applications to ...
3. [2022/1194] Multi-Authority ABE from Lattices without Random ...
4. [2022/1195] A Deep Neural Differential Distinguisher for ARX ...
5. [2022/1196] Embedded Identity Traceable Identity-Based IPFE ...
6. [2022/1197] On Squaring Modulo Mersenne Numbers
7. [2022/1198] To Be, or Not to Be Stateful: Post-Quantum Secure ...
8. [2022/1199] Structure Evaluation of AES-like Ciphers against ...
9. [2022/1200] SEEK: model extraction attack against hybrid secure ...
10. [2022/1201] Consistent, Efficient and Leakage-Model Free Mutual ...
11. [2022/1202] Disorientation faults in CSIDH
12. [2022/1203] On Module Unique-SVP and NTRU
13. [2022/1204] The Pseudorandom Oracle Model and Ideal Obfuscation
14. [2022/1205] Accountable Light Client Systems for PoS Blockchains
15. [2022/1206] On the Optimal Communication Complexity of Error- ...
16. [2022/1207] Attaining GOD Beyond Honest Majority With Friends ...
17. [2022/1208] Notes on Reusable Garbling
18. [2022/1209] Puncturable Key Wrapping and Its Applications
19. [2022/1210] On the Field-Based Division Property: Applications ...
20. [2022/1211] Arithmetization of Functional Program Execution via ...
21. [2022/1212] VoteXX: A Solution to Improper Influence in Voter- ...
22. [2022/1213] Nostradamus goes Quantum
23. [2022/1214] Updatable NIZKs from Non-Interactive Zaps
24. [2022/1215] Continuous Authentication in Secure Messaging
25. [2022/1216] A summary on the FRI low degree test
26. [2022/1217] Privacy-Preserving Authenticated Key Exchange in ...
27. [2022/1218] Stretching Cube Attacks: Improved Methods to ...
28. [2022/1219] Anonymous Random Allocation and Its Applications
29. [2022/1220] Permissionless Clock Synchronization with Public Setup
30. [2022/1221] Multi-User Security of the Sum of Truncated Random ...
31. [2022/1222] Homomorphic Encryption on GPU
32. [2022/1223] Efficient Proofs of Software Exploitability for ...
33. [2022/1224] From Plaintext-extractability to IND-CCA Security
34. [2022/1225] Hybrid Post-Quantum Signatures in Hardware Security ...
35. [2022/1226] Algebraic Relation of Three MinRank Algebraic Modelings
36. [2022/1227] How to Sample a Discrete Gaussian (and more) from a ...
37. [2022/1228] SCARF: A Low-Latency Block Cipher for Secure Cache- ...
38. [2022/1229] Cumulatively All-Lossy-But-One Trapdoor Functions ...

## 2022/1192

* Title: (Augmented) Broadcast Encryption from Identity Based Encryption with Wildcard
* Authors: Anaïs Barthoulot, Olivier Blazy, Sébastien Canard
* [Permalink](https://eprint.iacr.org/2022/1192)
* [Download](https://eprint.iacr.org/2022/1192.pdf)

### Abstract

Several broadcast encryption (BE) constructions have been proposed since Fiat and Naor introduced the concept, some achieving short parameters size while others achieve better security. Since 1994, a lot of alternatives to BE have moreover been additionally proposed, such as the broadcast and trace (BT) primitive which is a combination of broadcast encryption and traitor tracing. Among the other variants of BE, the notion of augmented BE (AugBE), introduced by Boneh and Waters in 2006, corresponds to a BE scheme with the particularity that the encryption algorithm takes an index as an additional parameter. If an AugBE scheme is both message and index hiding, it has been proved that it can generically be used to construct a secure BT scheme. Hence, any new result related to the former gives an improvement to the latter. In this paper, we first show that both BE and AugBE can be obtained by using an identity-based encryption scheme with wildcard (WIBE). We also introduce the new notion of anonymous AugBE, where the used users set is hidden, and prove that it implies index hiding. We then provide two different WIBE constructions. The first one has constant size ciphertext and used to construct a new constant size ciphertext BE scheme with adaptive CPA security, in the standard model (under the $\SXDH{}$ assumption). The second WIBE provides pattern-hiding, a new definition we introduced, and serves as a basis for the first anonymous AugBE scheme (and subsequently a BT scheme since our scheme is also index hiding by nature) in the literature, with adaptive security in the standard model (under the $\XDLin{}$ assumption).



## 2022/1193

* Title: Knowledge Encryption and Its Applications to Simulatable Protocols With Low Round-Complexity
* Authors: Yi Deng, Xinxuan Zhang
* [Permalink](https://eprint.iacr.org/2022/1193)
* [Download](https://eprint.iacr.org/2022/1193.pdf)

### Abstract

We introduce a new notion of public key encryption, knowledge encryption, for which its ciphertexts can be reduced to the public-key, i.e., any algorithm that can break the ciphertext indistinguishability can be used to extract the (partial) secret key. We show that knowledge encryption can be built solely on any two-round oblivious transfer with game-based security, which are known based on various standard (polynomial-hardness) assumptions, such as the DDH, the Quadratic($N^{th}$) Residuosity or the LWE assumption.

We use knowledge encryption to construct the first three-round (weakly) simulatable oblivious transfer. This protocol satisfies (fully) simulatable security for the receiver, and weakly simulatable security ($(T, \epsilon)$-simulatability) for the sender in the following sense: for any polynomial $T$ and any inverse polynomial $\epsilon$, there exists an efficient simulator such that the distinguishing gap of any distinguisher of size less than $T$ is at most $\epsilon$.

Equipped with these tools, we construct a variety of fundamental cryptographic protocols with low round-complexity, assuming only the existence of two-round oblivious transfer with game-based security. These protocols include three-round delayed-input weak zero knowledge argument, three-round weakly secure two-party computation, three-round concurrent weak zero knowledge in the BPK model, and a two-round commitment with weak security under selective opening attack. These results improve upon the assumptions required by the previous constructions. Furthermore, all our protocols enjoy the above $(T, \epsilon)$-simulatability (stronger than the distinguisher-dependent simulatability), and are
quasi-polynomial time simulatable under the same (polynomial hardness) assumption.



## 2022/1194

* Title: Multi-Authority ABE from Lattices without Random Oracles
* Authors: Brent Waters, Hoeteck Wee, David J. Wu
* [Permalink](https://eprint.iacr.org/2022/1194)
* [Download](https://eprint.iacr.org/2022/1194.pdf)

### Abstract

Attribute-based encryption (ABE) extends public-key encryption to enable fine-grained control to encrypted data. However, this comes at the cost of needing a central trusted authority to issue decryption keys. A multi-authority ABE (MA-ABE) scheme decentralizes ABE and allows anyone to serve as an authority. Existing constructions of MA-ABE only achieve security in the random oracle model.

In this work, we develop new techniques for constructing MA-ABE for the class of subset policies (which captures policies such as conjunctions and DNF formulas) whose security can be based in the plain model without random oracles. We achieve this by relying on the recently-proposed "evasive" learning with errors (LWE) assumption by Wee (EUROCRYPT 2022) and Tsabury (CRYPTO 2022).

Along the way, we also provide a modular view of the MA-ABE scheme for DNF formulas by Datta et al. (EUROCRYPT 2021) in the random oracle model. We formalize this via a general version of a related-trapdoor LWE assumption by Brakerski and Vaikuntanathan (ITCS 2022), which can in turn be reduced to the plain LWE assumption. As a corollary, we also obtain an MA-ABE scheme for subset policies from plain LWE with a polynomial modulus-to-noise ratio in the random oracle model. This improves upon the Datta et al. construction which relied on LWE with a sub-exponential modulus-to-noise ratio. Moreover, we are optimistic that the generalized related-trapdoor LWE assumption will also be useful for analyzing the security of other lattice-based constructions.



## 2022/1195

* Title: A Deep Neural Differential Distinguisher for ARX based Block Cipher
* Authors: Debranjan Pal, Upasana Mandal, Mainak Chaudhury, Abhijit Das, Dipanwita Roy Chowdhury
* [Permalink](https://eprint.iacr.org/2022/1195)
* [Download](https://eprint.iacr.org/2022/1195.pdf)

### Abstract

Over the last few years, deep learning is becoming the most trending topic
for the classical cryptanalysis of block ciphers. Differential cryptanalysis
is one of the primary and potent attacks on block ciphers. Here we apply
deep learning techniques to model differential cryptanalysis more easily.
In this paper, we report a generic tool using deep neural classifier that
assists to find differential distinguishers for block ciphers with reduced
round. We apply this approach for the differential cryptanalysis of ARX-
based encryption schemes HIGHT, LEA, and SPARX. The result shows
that our deep learning based distinguishers work with high accuracy for
14-round HIGHT, 13-Round LEA and 11-round SPARX. We also achieve
an improvement of the lower bound of data complexity for these three
ARX based ciphers.



## 2022/1196

* Title: Embedded Identity Traceable Identity-Based IPFE from Pairings and Lattices
* Authors: Subhranil Dutta, Tapas Pal, Amit Kumar Singh, Sourav Mukhopadhyay
* [Permalink](https://eprint.iacr.org/2022/1196)
* [Download](https://eprint.iacr.org/2022/1196.pdf)

### Abstract

We present the first fully collusion resistant traitor tracing (TT) scheme for identity-based inner product functional encryption (IBIPFE) that directly traces user identities through an efficient tracing procedure. We name such a scheme as embedded identity traceable IBIPFE (EI-TIBIPFE), where secret keys and ciphertexts are computed for vectors u and v respectively. Additionally, each secret key is associated with a user identification information tuple (i , id, gid) that specifies user index i , user identity id and an identity gid of a group to which the user belongs. The ciphertexts are generated under a group identity gid′ so that decryption recovers the inner product between the vectors u and v if the user is a member of the group gid′, i.e., gid = gid′. Suppose some users linked to a particular group team up and create a pirate decoder that is capable of decrypting the content of the group, then the tracing algorithm extracts at least one id from the team given black-box access to the decoder.
In prior works, such TT schemes are built for usual public key encryptions. The only existing TIPFE scheme proposed by Do, Phan, and Pointcheval [CT-RSA’20] can trace user indices but not the actual identities. Moreover, their scheme achieves selective security and private traceability, meaning that it is only the trusted authority that is able to trace user indices. In this work, we present the following TT schemes with varying parameters and levels of security:
(1) We generically construct EI-TIBIPFE assuming the existence of IBIPFE. The scheme preserves the security level of the underlying IBIPFE.
(2) We build an adaptively secure EI-TIPFE scheme from bilinear maps. Note that EI-TIPFE is a particular case of EI-TIBIPFE, which does not consider group identities.
(3) Next, we construct a selectively secure EI-TIBIPFE from bilinear maps. As an intermediate step, we design the first IBIPFE scheme based on a target group assumption in the standard model.
(4) Finally, we provide a generic construction of selectively secure EI-TIBIPFE from lattices, namely under the standard Learning With Errors assumption.
Our pairing-based schemes support public traceability and the ciphertext size grows with $\sqrt{n}$, whereas in the IBIPFE and lattice-based ones, it grows linearly with n. The main technical difficulty is designing such an advanced TT scheme for an IBIPFE that is beyond IPFE and more suitable for real-life applications.



## 2022/1197

* Title: On Squaring Modulo Mersenne Numbers
* Authors: David Naccache, Ofer Yifrach-Stav
* [Permalink](https://eprint.iacr.org/2022/1197)
* [Download](https://eprint.iacr.org/2022/1197.pdf)

### Abstract

During the design of a new primitive inspired by Squash we accidentally stumbled on the observation described in this note.

Let $n$ be a $k$-bit Mersenne number whose factors are unknown. Consider an $\ell$-bit secret number $x=2^{k/2}a+b$. We observe that there are parameter configurations where a chunk of the value $b^2$ is leaked even if $k<2\ell$.

This observation does not endanger any known scheme and in particular not Squash.



## 2022/1198

* Title: To Be, or Not to Be Stateful: Post-Quantum Secure Boot using Hash-Based Signatures
* Authors: Alexander Wagner, Felix Oberhansl, Marc Schink
* [Permalink](https://eprint.iacr.org/2022/1198)
* [Download](https://eprint.iacr.org/2022/1198.pdf)

### Abstract

While research in post-quantum cryptography (PQC) has gained
significant momentum, it is only slowly adopted for real-world
products. This is largely due to concerns about practicability and
maturity. The secure boot process of embedded devices is one s-
cenario where such restraints can result in fundamental security
problems. In this work, we present a flexible hardware/software
co-design for hash-based signature (HBS) schemes which enables
the move to a post-quantum secure boot today. These signature
schemes stand out due to their straightforward security proofs and
are on the fast track to standardisation. In contrast to previous
works, we exploit the performance intensive similarities of the s-
tateful LMS and XMSS schemes as well as the stateless SPHINCS+
scheme. Thus, we enable designers to use a stateful or stateless
scheme depending on the constraints of each individual application.
To show the feasibility of our approach, we compare our results
with hardware accelerated implementations of classical asymmetric
algorithms. Further, we lay out the usage of different HBS schemes
during the boot process. We compare different schemes, show the
importance of parameter choices, and demonstrate the performance
gain with different levels of hardware acceleration.



## 2022/1199

* Title: Structure Evaluation of AES-like Ciphers against Mixture Differential Cryptanalysis
* Authors: Xiaofeng Xie, Tian Tian
* [Permalink](https://eprint.iacr.org/2022/1199)
* [Download](https://eprint.iacr.org/2022/1199.pdf)

### Abstract

In ASIACRYPT 2017, Rønjom et al. analyzed AES with yoyo attack. Inspired by their 4-round AES distinguisher, Grassi proposed the mixture differential cryptanalysis as well as a key recovery attack on 5-round AES, which was shown to be better than the classical square attack in computation complexity.
After that, Bardeh et al. combined the exchange attack with the 4-round mixture differential distinguisher of AES, leading to the first secret-key chosen plaintext distinguisher for 6-round AES. Unlike the attack on 5-round AES, the result of 6-round key-recovery attack on AES has extremely large complexity, which implies the weakness of mixture difference to a certain extent. Our work aims at evaluating the security of AES-like ciphers against mixture differential cryptanalysis. We propose a new structure called a boomerang struncture and illustrate that a
differential distinguisher of a boomerang struncture just corresponds to a mixture differential distinguisher for AES-like ciphers. Based on the boomerang structure, it is shown that the mixture differential cryptanalysis is not suitable to be applied
to AES-like ciphers with high round number. In specific, we associate the primitive index with our framework built on the boomerang structure and give the upper bound for the length of mixture differentials with probability 1 on AES-like ciphers. It can be directly deduced from our framework that there is no mixture differential distinguisher for 6-round AES.



## 2022/1200

* Title: SEEK: model extraction attack against hybrid secure inference protocols
* Authors: Si Chen, Junfeng Fan
* [Permalink](https://eprint.iacr.org/2022/1200)
* [Download](https://eprint.iacr.org/2022/1200.pdf)

### Abstract

Security concerns about a machine learning model used in a prediction-as-a-service include the privacy of the model, the query and the result. Secure inference solutions based on homomorphic encryption (HE) and/or multiparty computation (MPC) have been developed to protect all the sensitive information. One of the most efficient type of solution utilizes HE for linear layers, and MPC for non-linear layers. However, for such hybrid protocols with semi-honest security, an adversary can malleate the intermediate features in the inference process, and extract model information more effectively than methods against inference service in plaintext. In this paper, we propose SEEK, a general extraction method for hybrid secure inference services outputing only class labels. This method can extract each layer of the target model independently, and is not affected by the depth of the model. For ResNet-18, SEEK can extract a parameter with less than 50 queries on average, with average error less than $0.03\%$.



## 2022/1201

* Title: Consistent, Efficient and Leakage-Model Free Mutual Information Estimation
* Authors: Arnab Roy, Aakash Chowdhury, Elisabeth Oswald
* [Permalink](https://eprint.iacr.org/2022/1201)
* [Download](https://eprint.iacr.org/2022/1201.pdf)

### Abstract

The mutual information between the observable device leakage and the unknown key is a key metric in the context of side channel attacks, evaluations, and countermeasures. Estimating this mutual information has been a problem and was addressed in several recent contributions. We explain why previous work has ended up in a "catch-22'' and we show how to avoid this situation by using a leakage model free estimation approach based on a recently discovered, consistent mutual information estimator. Our work demonstrates that mutual information estimation in the side channel setting can be done extremely efficiently (even in a multivariate setting), with strong mathematical guarantees, without the need for an explicit device leakage model, discretisation, or assumptions about the nature of the device leakage.



## 2022/1202

* Title: Disorientation faults in CSIDH
* Authors: Gustavo Banegas, Juliane Krämer, Tanja Lange, Michael Meyer, Lorenz Panny, Krijn Reijnders, Jana Sotáková, Monika Trimoska
* [Permalink](https://eprint.iacr.org/2022/1202)
* [Download](https://eprint.iacr.org/2022/1202.pdf)

### Abstract

We investigate a new class of fault-injection attacks against the CSIDH family of cryptographic group actions. Our disorientation attacks effectively flip the direction of some isogeny steps. We achieve this by faulting a specific subroutine, connected to the Legendre symbol or Elligator computations performed during the evaluation of the group action. These subroutines are present in almost all known CSIDH implementations. Post-processing a set of faulty samples allows us to infer constraints on the secret key. The details are implementation specific, but we show that in many cases, it is possible to recover the full secret key with only a modest number of successful fault injections and modest computational resources. We provide full details for attacking the original CSIDH proof-of-concept software as well as the CTIDH constant-time implementation. Finally, we present a set of lightweight countermeasures against the attack and discuss their security.



## 2022/1203

* Title: On Module Unique-SVP and NTRU
* Authors: Joël Felderhoff, Alice Pellet-Mary, Damien Stehlé
* [Permalink](https://eprint.iacr.org/2022/1203)
* [Download](https://eprint.iacr.org/2022/1203.pdf)

### Abstract

The NTRU problem can be viewed as an instance of finding a short non-zero vector in a lattice, under the promise that it contains an exceptionally short vector. Further, the lattice under scope has the structure of a rank-2 module over the ring of integers of a number field. Let us refer to this problem as the module unique Shortest Vector Problem,or mod-uSVP for short. We exhibit two reductions that together provide evidence the NTRU problem is not just a particular case of mod-uSVP, but representative of it from a computational perspective.

First, we reduce worst-case mod-uSVP to worst-case NTRU. For this, we rely on an oracle for id-SVP, the problem of finding short non-zero vectors in ideal lattices. Using the worst-case id-SVP to worst-case NTRU reduction from Pellet-Mary and Stehlé [ASIACRYPT'21],this shows that worst-case NTRU is equivalent to worst-case mod-uSVP.

Second, we give a random self-reduction for mod-uSVP. We put forward a distribution D over mod-uSVP instances such that solving mod-uSVP with a non-negligible probability for samples from D allows to solve mod-uSVP in the worst-case. With the first result, this gives a reduction from worst-case mod-uSVP to an average-case version of NTRU where the NTRU instance distribution is inherited from D. This worst-case to average-case reduction requires an oracle for id-SVP.



## 2022/1204

* Title: The Pseudorandom Oracle Model and Ideal Obfuscation
* Authors: Aayush Jain, Huijia Lin, Ji Luo, Daniel Wichs
* [Permalink](https://eprint.iacr.org/2022/1204)
* [Download](https://eprint.iacr.org/2022/1204.pdf)

### Abstract

We introduce a new idealized model of hash functions, which we refer to as the *pseudorandom oracle* (PrO) model. Intuitively, it allows us to model cryptosystems that use the code of a hash function in a non-black-box way. Formally, we model hash functions via a combination of a pseudorandom function (PRF) family and an ideal oracle. A user can initialize the hash function by choosing a PRF key $k$ and the oracle maps it to a public handle $h$. Given the handle $h$ and some input $x$, the oracle will recover the PRF key $k$ and evaluate the PRF on $x$. A user who chooses the PRF key $k$ therefore has a complete description of the hash function and can use its code in non-black-box constructions, while an adversary, who just gets the handle $h$, only has black-box access to the hash function via the oracle.

As our main result, we show how to construct ideal obfuscation in the PrO model, starting from functional encryption (FE), which in turn can be based on well-studied polynomial hardness assumptions. In contrast, we know that ideal obfuscation cannot be instantiated in the basic random oracle model under any assumptions. We believe our result gives a heuristic justification for the following: (1) most natural security goals implied by ideal obfuscation are achievable in the real world; (2) we can construct obfuscation from FE with polynomial security loss.

We also discuss how to interpret our result in the PrO model as a construction of ideal obfuscation using simple hardware tokens or as a way to bootstrap ideal obfuscation for PRFs to that for all functions.



## 2022/1205

* Title: Accountable Light Client Systems for PoS Blockchains
* Authors: Oana Ciobotaru, Fatemeh Shirazi, Alistair Stewart, Sergey Vasilyev
* [Permalink](https://eprint.iacr.org/2022/1205)
* [Download](https://eprint.iacr.org/2022/1205.pdf)

### Abstract

A major challenge for blockchain interoperability is having an on-chain light client protocol that is both efficient and secure. We present a protocol that provides short proofs about the state of a decentralised consensus protocol while being able to detect misbehaving parties. To do this naively, a verifier would need to maintain an updated list of all participants' public keys which makes the corresponding proofs long. In general, existing solutions either lack accountability or are not efficient. We define and design a committee key scheme with short proofs that do not include any of the individual participants' public keys in plain. Our committee key scheme, in turn, uses a custom designed SNARK which has a fast prover time. Moreover, using our committee key scheme, we define and design an accountable light client system as the main cryptographic core for building bridges between proof of stake blockchains. Finally, we implement a prototype of our custom SNARK for which we provide benchmarks.



## 2022/1206

* Title: On the Optimal Communication Complexity of Error-Correcting Multi-Server PIR
* Authors: Reo Eriguchi, Kaoru Kurosawa, Koji Nuida
* [Permalink](https://eprint.iacr.org/2022/1206)
* [Download](https://eprint.iacr.org/2022/1206.pdf)

### Abstract

An $\ell$-server Private Information Retrieval (PIR) scheme enables a client to retrieve a data item from a database replicated among $\ell$ servers while hiding the identity of the item. It is called $b$-error-correcting if a client can correctly compute the data item even in the presence of $b$ malicious servers. It is known that $b$-error correction is possible if and only if $\ell>2b$. In this paper, we first prove that if error correction is perfect, i.e., the client always corrects errors, the minimum communication cost of $b$-error-correcting $\ell$-server PIR is asymptotically equal to that of regular $(\ell-2b)$-server PIR as a function of the database size $n$. Secondly, we formalize a relaxed notion of statistical $b$-error-correcting PIR, which allows non-zero failure probability. We show that as a function of $n$, the minimum communication cost of statistical $b$-error-correcting $\ell$-server PIR is asymptotically equal to that of regular $(\ell-b)$-server one, which is at most that of $(\ell-2b)$-server one. Our main technical contribution is a generic construction of statistical $b$-error-correcting $\ell$-server PIR for any $\ell>2b$ from regular $(\ell-b)$-server PIR. We can therefore reduce the problem of determining the optimal communication complexity of error-correcting PIR to determining that of regular PIR. In particular, our construction instantiated with the state-of-the-art PIR schemes and the previous lower bound for single-server PIR result in a separation in terms of communication cost between perfect and statistical error correction for any $\ell>2b$.



## 2022/1207

* Title: Attaining GOD Beyond Honest Majority With Friends and Foes
* Authors: Aditya Hegde, Nishat Koti, Varsha Bhat Kukkala, Shravani Patil, Arpita Patra, Protik Paul
* [Permalink](https://eprint.iacr.org/2022/1207)
* [Download](https://eprint.iacr.org/2022/1207.pdf)

### Abstract

In the classical notion of multiparty computation (MPC), an honest party learning private inputs of others, either as a part of protocol specification or due to a malicious party's unspecified messages, is not considered a potential breach. Several works in the literature exploit this seemingly minor loophole to achieve the strongest security of guaranteed output delivery via a trusted third party, which nullifies the purpose of MPC. Alon et al. (CRYPTO 2020) presented the notion of Friends and Foes ($\mathtt{FaF}$) security, which accounts for such undesired leakage towards honest parties by modelling them as semi-honest (friends) who do not collude with malicious parties (foes). With real-world applications in mind, it's more realistic to assume parties are semi-honest rather than completely honest, hence it is imperative to design efficient protocols conforming to the $\mathtt{FaF}$ security model.

Our contributions are not only motivated by the practical viewpoint, but also consider the theoretical aspects of $\mathtt{FaF}$ security. We prove the necessity of semi-honest oblivious transfer for $\mathtt{FaF}$-secure protocols with optimal resiliency. On the practical side, we present QuadSquad, a ring-based 4PC protocol, which achieves fairness and GOD in the $\mathtt{FaF}$ model, with an optimal corruption of $1$ malicious and $1$ semi-honest party. QuadSquad is, to the best of our knowledge, the first practically efficient $\mathtt{FaF}$ secure protocol with optimal resiliency. Its performance is comparable to the state-of-the-art dishonest majority protocols while improving the security guarantee from abort to fairness and GOD. Further, QuadSquad elevates the security by tackling a stronger adversarial model over the state-of-the-art honest-majority protocols, while offering a comparable performance for the input-dependent computation. We corroborate these claims by benchmarking the performance of QuadSquad. We also consider the application of liquidity matching that deals with highly sensitive financial transaction data, where $\mathtt{FaF}$ security is apt. We design a range of $\mathtt{FaF}$ secure building blocks to securely realize liquidity matching as well as other popular applications such as privacy-preserving machine learning (PPML). Inclusion of these blocks makes QuadSquad a comprehensive framework.



## 2022/1208

* Title: Notes on Reusable Garbling
* Authors: Hu Yupu, Dong Siyue, Wang Baocang, Liu Jun
* [Permalink](https://eprint.iacr.org/2022/1208)
* [Download](https://eprint.iacr.org/2022/1208.pdf)

### Abstract

Garbling is a cryptographic primitive which has many applications. It is mainly used for scenes of limited authority, such as multi-party computation (MPC), attribute-based encryption (ABE), functional encryption (FE), indistinguishability obfuscation (IO), etc. Garbling schemes before 2013 are of one-time garbling. Goldwasser et al and Agrawal presented a reusable garbling scheme, which made use of a symmetric encryption scheme and an FE scheme as the components.

In this paper we discuss the validity and the efficiency of reusable garbling scheme. We present the following three notes on the scheme.

(1) Reusable garbling scheme does not provide new applications, and it is still a one-time garbling scheme.

(2) Even reusable garbling scheme is taken as a one-time garbling scheme, sometimes it is not usable. More detailedly, it can only be used for Basic Scene 2, and cannot be used for Basic Scene 1. For example, it cannot be used for MPC.

(3) Even reusable garbling scheme is taken as a one-time garbling scheme used for Basic Scene 2, there is no evidence to show that its efficiency is better than a former one-time garbling scheme.



## 2022/1209

* Title: Puncturable Key Wrapping and Its Applications
* Authors: Matilda Backendal, Felix Günther, Kenneth G. Paterson
* [Permalink](https://eprint.iacr.org/2022/1209)
* [Download](https://eprint.iacr.org/2022/1209.pdf)

### Abstract

We introduce puncturable key wrapping (PKW), a new cryptographic primitive that supports fine-grained forward security properties in symmetric key hierarchies. We develop syntax and security definitions, along with provably secure constructions for PKW from simpler components (AEAD schemes and puncturable PRFs). We show how PKW can be applied in two distinct scenarios. First, we show how to use PKW to achieve forward security for TLS 1.3 0-RTT session resumption, even when the server's long-term key for generating session tickets gets compromised. This extends and corrects a recent work of Aviram, Gellert, and Jager (Journal of Cryptology, 2021). Second, we show how to use PKW to build a protected file storage system with file shredding, wherein a client can outsource encrypted files to a potentially malicious or corrupted cloud server whilst achieving strong forward-security guarantees, relying only on local key updates.



## 2022/1210

* Title: On the Field-Based Division Property: Applications to MiMC, Feistel MiMC and GMiMC (Full Version)
* Authors: Jiamin Cui, Kai Hu, Meiqin Wang, Puwen Wei
* [Permalink](https://eprint.iacr.org/2022/1210)
* [Download](https://eprint.iacr.org/2022/1210.pdf)

### Abstract

Recent practical applications using advanced cryptographic protocols such as multi-party computations (MPC) and zero-knowledge proofs (ZKP) have prompted a range of novel symmetric primitives described over large finite fields, characterized as arithmetization-oriented AO ciphers. Such designs, aiming to minimize the number of multiplications over fields, have a high risk of being vulnerable to algebraic attacks, especially to the higher-order differential attack. Thus, it is significant to carefully evaluate the growth of their algebraic degree. However, the degree estimation for AO ciphers has been a challenge for cryptanalysts due to the lack of general and accurate methods.

In this paper, we extend the division property, a state-of-the-art framework for finding the upper bound of the algebraic degree over binary fields, to the scope of $\mathbb{F}_{2^n}$. It is a generic method to detect the algebraic degree for AO ciphers, even applicable to Feistel ciphers which have no better bounds than the trivial exponential one. In this general division property, our idea is to evaluate whether the polynomial representation of a block cipher contains some specific monomials. With a deep investigation of the arithmetical feature, we introduce the propagation rules of monomials for field-based operations, which can be efficiently modeled using the bit-vector theory of SMT. Then the new searching tool for degree estimation can be constructed due to the relationship between the algebraic degree and the exponents of monomials.

We apply our new framework to some important AO ciphers, including Feistel MiMC, GMiMC, and MiMC. For Feistel MiMC, we show that the algebraic degree grows significantly slower than the native exponential bound. For the first time, we present a secret-key higher-order differential distinguisher for up to 124 rounds, much better than the 83-round distinguisher for Feistel MiMC permutation proposed at CRYPTO 2020. We also exhibit a full-round zero-sum distinguisher with a data complexity of $2^{251}$. Our method can be further extended for the general Feistel structure with more branches and exhibit higher-order differential distinguishers against the practical instance of GMiMC for up to 50 rounds. For MiMC in SP-networks, our results correspond to the exact algebraic degree proved by Bouvier et al. We also point out that the number of rounds in MiMC's specification is not sufficient to guarantee the security against the higher-order differential attack for MiMC-like schemes with different exponents. The investigation of different exponents provides some guidance on the cipher design.



## 2022/1211

* Title: Arithmetization of Functional Program Execution via Interaction Nets in Halo 2
* Authors: Anthony Hart
* [Permalink](https://eprint.iacr.org/2022/1211)
* [Download](https://eprint.iacr.org/2022/1211.pdf)

### Abstract

We sketch a method for creating a zero-knowledge proof of knowledge for the correct execution of a program within a model of higher-order, recursive, purely functional programming by leveraging Halo 2. To our knowledge, this is the first ZKP for general purpose computation based on purely functional computation. This is an attractive alternative to using a von Neumann architecture based zero-knowledge virtual machine for verified computing of functional programs, as compilation will be more direct, making it more easily verifiable and potentially more efficient.
Interaction nets are a natural setting for recursive, higher-order functional programming where all computation steps are linear and local. Interaction nets are graphs and traces for such programs are hyper-graphs. Correctness of a trace is a simple syntactic check over the structure of the trace represented as a hyper-graph. We reformulate this syntactic check as a Halo 2 circuit which is universal over all traces.



## 2022/1212

* Title: VoteXX: A Solution to Improper Influence in Voter-Verifiable Elections
* Authors: David Chaum, Richard T. Carback, Jeremy Clark, Chao Liu, Mahdi Nejadgholi, Bart Preneel, Alan T. Sherman, Mario Yaksetig, Zeyuan Yin, Filip Zagórski, Bingsheng Zhang
* [Permalink](https://eprint.iacr.org/2022/1212)
* [Download](https://eprint.iacr.org/2022/1212.pdf)

### Abstract

We solve a long-standing challenge to the integrity of votes cast without the supervision of a voting booth: “improper influence,” which we define as any combination of vote buying and voter coercion. Our approach allows each voter, or their trusted agent(s), to cancel their vote in a way that is unstoppable, irrevocable, and forever unattributable to the voter. In particular, our approach enhances security of online, remote, public-sector elections, for which there is a growing need and the threat of improper influence is most acute. In this extended abstract, we introduce the new approach, compare it with previous methods, and concisely summarize the protocols. In our full paper, we give detailed cryptographic protocols, show how they can be applied to several voting settings, describe our implementation in a full voting system called VoteXX, and provide UC proofs. Our system protects against the strongest adversary considered in prior related work and is suitable for widespread use in public elections.



## 2022/1213

* Title: Nostradamus goes Quantum
* Authors: Barbara Jiabao Benedikt, Marc Fischlin, Moritz Huppert
* [Permalink](https://eprint.iacr.org/2022/1213)
* [Download](https://eprint.iacr.org/2022/1213.pdf)

### Abstract

In the Nostradamus attack, introduced by Kelsey and Kohno (Eurocrypt 2006), the adversary has to commit to a hash value y of an iterated hash function H such that, when later given a message prefix P, the adversary is able to find a suitable "suffix explanation" S with H(P||S)=y. Kelsey and Kohno show a herding attack with $2^{2n/3}$ evaluations of the compression function of H (with n bits output and state), locating the attack between preimage attacks and collision search in terms of complexity. Here we investigate the security of Nostradamus attacks for quantum adversaries. We present a quantum herding algorithm for the Nostradamus problem making approximately $\sqrt[3]{n}\cdot 2^{3n/7}$ compression function evaluations, significantly improving over the classical bound. We also prove that quantum herding attacks cannot do better than $2^{3n/7}$ evaluations for random compression functions, showing that our algorithm is (essentially) optimal. We also discuss a slightly less tight bound of roughly $2^{3n/7-s}$ for general Nostradamus attacks against random compression functions, where s is the maximal block length of the adversarially chosen suffix S.



## 2022/1214

* Title: Updatable NIZKs from Non-Interactive Zaps
* Authors: Karim Baghery, Navid Ghaedi Bardeh
* [Permalink](https://eprint.iacr.org/2022/1214)
* [Download](https://eprint.iacr.org/2022/1214.pdf)

### Abstract

In ASIACRYPT 2016, Bellare, Fuchsbauer, and Scafuro studied the security of NIZK arguments under subverted Structured Reference String (SRS) and presented some positive and negative results. In their best positive result, they showed that by defining an SRS as a tuple of knowledge assumption in bilinear groups (e.g. $g^a, g^b, g^{ab}$), and then using a Non-Interactive (NI) zap to prove that either there is a witness for the statement $\mathsf{x}$ or one knows the trapdoor of SRS (e.g. $a$ or $b$), one can build NIZK arguments that can achieve soundness and $\textit{subversion zero-knowledge}$ (zero-knowledge without trusting a third party; Sub-ZK). In this paper, we expand their idea and use NI zaps (of knowledge) to build NIZK arguments (of knowledge) with $\textit{updatable}$, $\textit{universal}$, and $\textit{succinct}$ SRS. To this end, we first show that their proposed sound and Sub-ZK NIZK argument can also achieve $\textit{updatable}$ soundness, which is a more desired notion than the plain soundness. Updatable soundness allows the verifier to update the SRS one time and bypass the need for a trusted third party. Then, we show that using a similar OR language, given a NI zap (of knowledge) and a $\textit{key-updatable}$ signature scheme, one can build NIZK arguments that can achieve Sub-ZK and $\textit{updatable}$ simulation soundness (resp. $\textit{updatable}$ simulation extractability). The proposed constructions are the first NIZK arguments that have updatable and succinct SRS, and do not require a random oracle. Our instantiations show that in the resulting NIZK arguments the computational cost for the parties to verify/update the SRS is negligible, namely, a few exponentiations and pairing checks. The run times of the prover and verifier, as well as the size of the proof, are asymptotically the same as those of the underlying NI zap.



## 2022/1215

* Title: Continuous Authentication in Secure Messaging
* Authors: Benjamin Dowling, Felix Günther, Alexandre Poirrier
* [Permalink](https://eprint.iacr.org/2022/1215)
* [Download](https://eprint.iacr.org/2022/1215.pdf)

### Abstract

Secure messaging schemes such as the Signal protocol rely on out-of-band channels to verify the authenticity of long-running communication. Such out-of-band checks however are only rarely actually performed by users in practice.

In this paper, we propose a new method for performing continuous authentication during a secure messaging session, without the need for an out-of-band channel. Leveraging the users' long-term secrets, our Authentication Steps extension guarantees authenticity as long as long-term secrets are not compromised, strengthening Signal's post-compromise security. Our mechanism further allows to detect a potential compromise of long-term secrets after the fact via an out-of-band channel.

Our protocol comes with a novel, formal security definition capturing continuous authentication, a general construction for Signal-like protocols, and a security proof for the proposed instantiation. We further provide a prototype implementation which seamlessly integrates on top of the official Signal Java library, together with bandwidth and storage overhead benchmarks.



## 2022/1216

* Title: A summary on the FRI low degree test
* Authors: Ulrich Haböck
* [Permalink](https://eprint.iacr.org/2022/1216)
* [Download](https://eprint.iacr.org/2022/1216.pdf)

### Abstract

This document is an informal summary on the FRI low degree test [BSBHR18a], [BSCI+20], and DEEP algebraic linking from [BSGKS20]. Based on its most recent soundness analysis [BSCI+20], we discuss parameter settings for practical security levels, how FRI is turned into a polynomial commitment scheme, and the soundness of DEEP sampling in the list decoding regime. In particular, we illustrate the DEEP method applied to proving satisfiability of algebraic intermediate representations and prove a soundness error bound which slightly improves the one in [Sta21].



## 2022/1217

* Title: Privacy-Preserving Authenticated Key Exchange in the Standard Model
* Authors: You Lyu, Shengli Liu, Shuai Han, Dawu Gu
* [Permalink](https://eprint.iacr.org/2022/1217)
* [Download](https://eprint.iacr.org/2022/1217.pdf)

### Abstract

Privacy-Preserving Authenticated Key Exchange (PPAKE) provides protection both for the session keys and the identity information of the involved parties. In this paper, we introduce the concept of robustness into PPAKE. Robustness enables each user to confirm whether itself is the target recipient of the first round message in the protocol. With the help of robustness, a PPAKE protocol can successfully avoid the heavy redundant communications and computations caused by the ambiguity of communicants in the existing PPAKE, especially in broadcast channels.

We propose a generic construction of robust PPAKE from key encapsulation mechanism (KEM), digital signature (SIG), message authentication code (MAC), pseudo-random generator (PRG) and symmetric encryption (SE). By instantiating KEM, MAC, PRG from the DDH assumption and SIG from the CDH assumption, we obtain a specific robust PPAKE scheme in the standard model, which enjoys forward security for session keys, explicit authentication and forward privacy for user identities. Thanks to the robustness of our PPAKE, the number of broadcast messages per run and the computational complexity per user are constant, and in particular, independent of the number of users in the system.



## 2022/1218

* Title: Stretching Cube Attacks: Improved Methods to Recover Massive Superpolies
* Authors: Jiahui He, Kai Hu, Bart Preneel, Meiqin Wang
* [Permalink](https://eprint.iacr.org/2022/1218)
* [Download](https://eprint.iacr.org/2022/1218.pdf)

### Abstract

Cube attacks exploit the algebraic properties of symmetric ciphers by recovering a special polynomial, the superpoly, and subsequently the secret key. When the algebraic normal forms of the corresponding Boolean functions are not available, the division property based approach allows to recover the exact superpoly in a clever way. However, the computational cost to recover the superpoly becomes prohibitive as the number of rounds of the cipher increases. For example, the nested monomial predictions (NMP) proposed at ASIACRYPT 2021 stuck at round 845 for Trivium. To alleviate the bottleneck of the NMP technique, i.e., the unsolvable model due to the excessive number of monomial trails, we shift our focus to the so-called valuable terms of a specific middle round that contribute to the superpoly. Two new techniques are introduced, namely, Non-zero Bit-based Division Property (NBDP) and Core Monomial Prediction (CMP), both of which result in a simpler MILP model compared to the MILP model of MP. It can be shown that the CMP technique offers a substantial improvement over the monomial prediction technique in terms of computational complexity of recovering valuable terms. Combining the divide-and-conquer strategy with these two new techniques, we catch the valuable terms more effectively and thus avoid wasting computational resources on intermediate terms contributing nothing to the superpoly. As an illustration of the power of our techniques, we apply our framework to Trivium, Grain, Kreyvium and Acorn. As a result, the computational cost of earlier attacks can be significantly reduced and the exact ANFs of the superpolies for 846-, 847- and 848-round Trivium, 192-round Grain, 895-round Kreyvium and 776-round Acorn can be recovered in practical time, even though the superpoly of 848-round Trivium contains over 500 million terms; this corresponds to respectively 3, 1, 1 and 1 rounds more than the previous best results. Moreover, by investigating the internal properties of Möbius transformation, we show how to perform key recovery using superpolies involving full key bits, which leads to the best key recovery attacks on the targeted ciphers.



## 2022/1219

* Title: Anonymous Random Allocation and Its Applications
* Authors: Azam Soleimanian
* [Permalink](https://eprint.iacr.org/2022/1219)
* [Download](https://eprint.iacr.org/2022/1219.pdf)

### Abstract

Random Allocation -the random assignment of the data to the parties- is a well-studied topic in the analysis of medical or judicial data, and the context of resource distribution. Random allocation reduces the chance of bias or corruption in the relevant applications, which makes the results more reliable. This is done by preventing a special or pre-planned assignment of the data to accommodate the assessment toward the desired results. This paper provides the first formal syntax and security notion of a random allocation scheme. Based on our new security notions of anonymity, confidentiality, and data-integrity, random allocation can cover more applications such as the distributed audit system where the confidentiality of data and the anonymity of auditors are of paramount importance. Our protocol allows the parties to stay anonymous during the concurrent executions of the protocol even if they have revealed themselves at a certain execution. The revelation property gives the possibility to the parties to claim certain advantages/faults at the end of a protocol-execution (without breaking the data-privacy or anonymity in other protocol-executions). We instantiate our syntax and prove the security based on simple cryptographic components and assumptions such as the Diffie-Hellman assumption, in the random oracle model.



## 2022/1220

* Title: Permissionless Clock Synchronization with Public Setup
* Authors: Juan Garay, Aggelos Kiayias, Yu Shen
* [Permalink](https://eprint.iacr.org/2022/1220)
* [Download](https://eprint.iacr.org/2022/1220.pdf)

### Abstract

The permissionless clock synchronization problem asks how it is possible for a population of parties to maintain a system-wide synchronized clock, while their participation rate fluctuates --- possibly very widely --- over time. The underlying assumption is that parties experience the passage of time with roughly the same speed, but however they may disengage and engage with the protocol following arbitrary (and even chosen adversarially) participation patterns. This (classical) problem has received renewed attention due to the advent of blockchain protocols, and recently it has been solved in the setting of proof of stake, i.e., when parties are assumed to have access to a trusted PKI setup [Badertscher et al., Eurocrypt ’21].

In this work, we present the first proof-of-work (PoW)-based permissionless clock synchronization protocol. Our construction assumes a public setup (e.g., a CRS) and relies on an honest majority of computational power that, for the first time, is described in a fine-grain timing model that does not utilize a global clock that exports the current time to all parties. As a secondary result of independent interest, our protocol gives rise to the first PoW-based ledger consensus protocol that does not rely on an external clock for the time-stamping of transactions and adjustment of the PoW difficulty.



## 2022/1221

* Title: Multi-User Security of the Sum of Truncated Random Permutations (Full Version)
* Authors: Wonseok Choi, Hwigyeom Kim, Jooyoung Lee, Yeongmin Lee
* [Permalink](https://eprint.iacr.org/2022/1221)
* [Download](https://eprint.iacr.org/2022/1221.pdf)

### Abstract

For several decades, constructing pseudorandom functions from pseudorandom permutations, so-called Luby-Rackoff backward construction, has been a popular cryptographic problem. Two methods are well-known and comprehensively studied for this problem: summing two random permutations and truncating partial bits of the output from a random permutation. In this paper, by combining both summation and truncation, we propose new Luby-Rackoff backward constructions, dubbed SaT1 and SaT2, respectively. SaT2 is obtained by partially truncating output bits from the sum of two independent random permutations, and SaT1 is its single permutation-based variant using domain separation. The distinguishing advantage against SaT1 and SaT2 is upper bounded by O(\sqrt{\mu q_max}/2^{n-0.5m}) and O({\sqrt{\mu}q_max^1.5}/2^{2n-0.5m}), respectively, in the multi-user setting, where n is the size of the underlying permutation, m is the output size of the construction, \mu is the number of users, and q_max is the maximum number of queries per user. We also prove the distinguishing advantage against a variant of XORP[3]~(studied by Bhattacharya and Nandi at Asiacrypt 2021) using independent permutations, dubbed SoP3-2, is upper bounded by O(\sqrt{\mu} q_max^2}/2^{2.5n})$. In the multi-user setting with \mu = O(2^{n-m}), a truncated random permutation provides only the birthday bound security, while SaT1 and SaT2 are fully secure, i.e., allowing O(2^n) queries for each user. It is the same security level as XORP[3] using three permutation calls, while SaT1 and SaT2 need only two permutation calls.



## 2022/1222

* Title: Homomorphic Encryption on GPU
* Authors: Ali Şah Özcan, Can Ayduman, Enes Recep Türkoğlu, Erkay Savaş
* [Permalink](https://eprint.iacr.org/2022/1222)
* [Download](https://eprint.iacr.org/2022/1222.pdf)

### Abstract

Homomorphic encryption (HE) is a cryptosystem that allows secure processing of encrypted data. One of the most popular HE schemes is the Brakerski-Fan-Vercauteren (BFV), which supports somewhat (SWHE) and fully homomorphic encryption (FHE). Since overly involved arithmetic operations of HE schemes are amenable to concurrent computation, GPU devices can be instrumental in facilitating the practical use of HE in real world applications thanks to their superior parallel processing capacity.

This paper presents an optimized and highly parallelized GPU library to accelerate the BFV scheme. This library includes state-of-the-art implementations of Number Theoretic Transform (NTT) and inverse NTT that minimize the GPU kernel function calls. It makes an efficient use of the GPU memory hierarchy and computes 128 NTT operations for ring dimension of $2^{14}$ only in $176.1~\mu s$ on RTX~3060Ti GPU. To the best of our knowlede, this is the fastest implementation in the literature. The library also improves the performance of the homomorphic operations of the BFV scheme. Although the library can be independently used, it is also fully integrated with the Microsoft SEAL library, which is a well-known HE library that also implements the BFV scheme. For one ciphertext multiplication, for the ring dimension $2^{14}$ and the modulus bit size of $438$, our GPU implementation offers $\mathbf{63.4}$ times speedup over the SEAL library running on a high-end CPU. The library compares favorably with other state-of-the-art GPU implementations of NTT and the BFV operations. Finally, we implement a privacy-preserving application that classifies encrpyted genome data for tumor types and achieve speedups of $42.98$ and $5.7$ over a CPU implementations using single and 16 threads, respectively. Our results indicate that GPU implementations can facilitate the deployment of homomorphic cryptographic libraries in real world privacy preserving applications.



## 2022/1223

* Title: Efficient Proofs of Software Exploitability for Real-world Processors
* Authors: Matthew Green, Mathias Hall-Andersen, Eric Hennenfent, Gabriel Kaptchuk, Benjamin Perez, Gijs Van Laer
* [Permalink](https://eprint.iacr.org/2022/1223)
* [Download](https://eprint.iacr.org/2022/1223.pdf)

### Abstract

We consider the problem of proving in zero-knowledge the existence of vulnerabilities in executables compiled to run on real-world processors. We demonstrate that it is practical to prove knowledge of real exploits for real-world processor architectures without the need for source code and without limiting our consideration to narrow vulnerability classes. To achieve this, we devise a novel circuit compiler and a toolchain that produces highly optimized, non-interactive zero-knowledge proofs for programs executed on the MSP430, an ISA commonly used in embedded hardware. Our toolchain employs a highly optimized circuit compiler and a number of novel optimizations to construct efficient proofs for program binaries. To demonstrate the capability of our system, we test our toolchain by constructing proofs for challenges in the Microcorruption capture the flag exercises.



## 2022/1224

* Title: From Plaintext-extractability to IND-CCA Security
* Authors: Ehsan Ebrahimi
* [Permalink](https://eprint.iacr.org/2022/1224)
* [Download](https://eprint.iacr.org/2022/1224.pdf)

### Abstract

We say a public-key encryption is plaintext-extractable in the random oracle model if there exists an algorithm that given access to all inputs/outputs queries to the random oracles can simulate the decryption oracle. We argue that plaintext-extractability is enough to show the indistinguishably under chosen ciphertext attack (IND-CCA) of OAEP+ transform (Shoup, Crypto 2001) when the underlying trapdoor permutation is one-way.

We extend the result to the quantum random oracle model (QROM) and show that OAEP+ is IND-CCA secure in QROM if the underlying trapdoor permutation is quantum one-way.



## 2022/1225

* Title: Hybrid Post-Quantum Signatures in Hardware Security Keys
* Authors: Diana Ghinea, Fabian Kaczmarczyck, Jennifer Pullman, Julien Cretin, Stefan Kölbl, Rafael Misoczki, Jean-Michel Picod, Luca Invernizzi, Elie Bursztein
* [Permalink](https://eprint.iacr.org/2022/1225)
* [Download](https://eprint.iacr.org/2022/1225.pdf)

### Abstract

Recent advances in quantum computing are increasingly jeopardizing the security of cryptosystems currently in widespread use, such as RSA or elliptic-curve signatures. To address this threat, researchers and standardization institutes have accelerated the transition to quantum-resistant cryptosystems, collectively known as Post-Quantum Cryptography (PQC). These PQC schemes present new challenges due to their larger memory and computational footprints and their higher chance of latent vulnerabilities.

In this work, we address these challenges by introducing a scheme to upgrade the digital signatures used by security keys to PQC, focusing on both its theoretical and practical aspects. Specifically, we introduce a hybrid digital signature scheme based on two building blocks: a classically-secure scheme, ECDSA, and a post-quantum secure one, Dilithium.
Our hybrid scheme maintains the guarantees of each underlying building block even if the other one is broken, thus being resistant to classical and quantum attacks. Additionally, our hybrid scheme ensures that an adversary cannot derive ECDSA or Dilithium signatures that this authentication protocol considers valid.
On the practical aspect, we experimentally show that our hybrid signature scheme can successfully execute on current security keys, even though secure PQC schemes are known to require substantial resources.

We publish an open-source implementation of our scheme at http://anonymous.4open.science/r/OpenSK-D018/ so that other researchers can reproduce our results on a nRF52840 development kit.



## 2022/1226

* Title: Algebraic Relation of Three MinRank Algebraic Modelings
* Authors: Hao Guo, Jintai Ding
* [Permalink](https://eprint.iacr.org/2022/1226)
* [Download](https://eprint.iacr.org/2022/1226.pdf)

### Abstract

We give algebraic relations among equations of three algebraic modelings for MinRank problem: support minors modeling, Kipnis–Shamir modeling and minors modeling.



## 2022/1227

* Title: How to Sample a Discrete Gaussian (and more) from a Random Oracle
* Authors: George Lu, Brent Waters
* [Permalink](https://eprint.iacr.org/2022/1227)
* [Download](https://eprint.iacr.org/2022/1227.pdf)

### Abstract

The random oracle methodology is central to the design of many practical
cryptosystems. A common challenge faced in several systems is the need to have
a random oracle that outputs from a structured distribution $\mathcal{D}$, even though most
heuristic implementations such as SHA-3 are best suited for outputting bitstrings.


Our work explores the problem of sampling from discrete Gaussian (and related) distributions in a manner that they can be programmed into random oracles. We make the following contributions:

-We provide a definitional framework for our results. We say that a sampling algorithm $\mathsf{Sample}$ for a distribution is explainable if there exists an algorithm $\mathsf{Explain}$ where, for a $x$ in the domain, we have that $\mathsf{Explain}(x) \rightarrow r \in \{0,1\}^n$ such that $\mathsf{Sample}(r)=x$. Moreover, if $x$ is sampled from $\mathcal{D}$ the explained distribution is statistically close to choosing $r$ uniformly at random. We consider a variant of this definition that allows the statistical closeness to be a "precision parameter'' given to the $\mathsf{Explain}$ algorithm. We show that sampling algorithms which satisfy our `explainability' property can be programmed as a random oracle.

-We provide a simple algorithm for explaining \emph{any} sampling algorithm that works over distributions with polynomial sized ranges. This includes discrete Gaussians with small standard deviations.

-We show how to transform a (not necessarily explainable) sampling algorithm $\mathsf{Sample}$ for a distribution into a new $\mathsf{Sample}'$ that is explainable. The requirements for doing this is that (1) the probability density function is efficiently computable (2) it is possible to efficiently uniformly sample from all elements that have a probability density above a given threshold $p$, showing the equivalence of random oracles to these distributions and random oracles to uniform bitstrings. This includes a large class of distributions, including all discrete Gaussians.

-A potential drawback of the previous approach is that the transformation requires an additional computation of the density function. We provide a more customized approach that shows the Miccancio-Walter discrete Gaussian sampler is explainable as is. This suggests that other discrete Gaussian samplers in a similar vein might also be explainable as is.



## 2022/1228

* Title: SCARF: A Low-Latency Block Cipher for Secure Cache-Randomization
* Authors: Federico Canale, Tim Güneysu, Gregor Leander, Jan Thoma, Yosuke Todo, Rei Ueno
* [Permalink](https://eprint.iacr.org/2022/1228)
* [Download](https://eprint.iacr.org/2022/1228.pdf)

### Abstract

Randomized cache architectures have proven to significantly
increase the complexity of contention-based cache side channel attacks
and therefore pre\-sent an important building block for side channel secure
microarchitectures. By
randomizing the address-to-cache-index mapping, attackers can
no longer trivially construct minimal eviction sets which are
fundamental for contention-based cache attacks. At the same time,
randomized caches maintain the flexibility of traditional caches,
making them broadly applicable across various CPU-types. This is
a major advantage over cache partitioning approaches.

A large variety of randomized cache architectures has been proposed.
However, the actual randomization function received little attention
and is often neglected in these proposals. Since the randomization operates
directly on the critical path of the cache lookup, the function needs
to have extremely low latency. At the same time, attackers must not be
able to bypass the randomization which would nullify the security benefit of the randomized mapping.
In this paper we propose \cipher (\underline{S}ecure \underline{CA}che \underline{R}andomization \underline{F}unction), the first dedicated cache randomization
cipher which achieves low latency and is cryptographically secure in the cache attacker model.
The design methodology for this dedicated cache cipher enters new territory in the field of block
ciphers with a small 10-bit block length and heavy key-dependency in few rounds.



## 2022/1229

* Title: Cumulatively All-Lossy-But-One Trapdoor Functions from Standard Assumptions
* Authors: Benoît Libert, Ky Nguyen, Alain Passelègue
* [Permalink](https://eprint.iacr.org/2022/1229)
* [Download](https://eprint.iacr.org/2022/1229.pdf)

### Abstract

Chakraborty, Prabhakaran, and Wichs (PKC'20) recently introduced a new tag-based variant of lossy trapdoor functions, termed cumulatively all-lossy-but-one trapdoor functions (CALBO-TDFs). Informally, CALBO-TDFs allow defining a public tag-based function with a (computationally hidden) special tag, such that the function is lossy for all tags except when the special secret tag is used. In the latter case, the function becomes injective and efficiently invertible using a secret trapdoor. This notion has been used to obtain advanced constructions of signatures with strong guarantees against leakage and tampering, and also by Dodis, Vaikunthanathan, and Wichs (EUROCRYPT'20) to obtain constructions of randomness extractors with extractor-dependent sources. While these applications are motivated by practical considerations, the only known instantiation of CALBO-TDFs so far relies on the existence of indistinguishability obfuscation.

In this paper, we propose the first two instantiations of CALBO-TDFs based on standard assumptions. Our constructions are based on the LWE assumption with a sub-exponential approximation factor and on the DCR assumption, respectively, and circumvent the use of indistinguishability obfuscation by relying on lossy modes and trapdoor mechanisms enabled by these assumptions.