[continued from previous message]

Given the need for progress on the basic fuzzy extractor primitive, it is prudent to seek generic mechanisms to transform a fuzzy extractor into one that is robust, private, and reusable so that it can inherit further improvements.
This work asks if one can generically upgrade fuzzy extractors to achieve robustness, privacy, and reusability. We show positive and negative results: we show upgrades for robustness and privacy, but we provide a negative result on reuse.
1. We upgrade (private) fuzzy extractors to be robust under weaker assumptions than previously known in the common reference string model.
2. We show a generic upgrade for a private fuzzy extractor using multi-bit compute and compare (MBCC) obfuscation (Wichs and Zirdelis, FOCS 2017) that requires less entropy than prior work.
3. We show one cannot arbitrarily compose private fuzzy extractors. It is known one cannot reuse an arbitrary fuzzy extractor; each enrollment can leak a constant fraction of the input entropy.
We show that one cannot build a reusable private fuzzy extractor by considering other enrollments as auxiliary input. In particular, we show that assuming MBCC obfuscation and collision-resistant hash functions, there does not exist a private fuzzy
extractor secure against unpredictable auxiliary inputs strengthening a negative result of Brzuska et al. (Crypto 2014).



## 2023/1942

* Title: Traceable mixnets
* Authors: Prashant Agrawal, Abhinav Nakarmi, Mahabir Prasad Jhanwar, Subodh Vishnu Sharma, Subhashis Banerjee
* [Permalink](https://eprint.iacr.org/2023/1942)
* [Download](https://eprint.iacr.org/2023/1942.pdf)

### Abstract

We introduce the notion of traceable mixnets. In a traditional mixnet, multiple mix-servers jointly permute and decrypt a list of ciphertexts to produce a list of plaintexts, along with a proof of correctness, such that the association between individual
ciphertexts and plaintexts remains completely hidden. However, in many applications, the privacy-utility tradeoff requires answering some specific queries about this association, without revealing any information beyond the query result. We consider
queries of the following types: a) given a ciphertext in the mixnet input list, whether it encrypts one of a given subset of plaintexts in the output list, and b) given a plaintext in the mixnet output list, whether it is a decryption of one of a given
subset of ciphertexts in the input list. Traceable mixnets allow the mix-servers to jointly prove answers to the above queries to a querier such that neither the querier nor a threshold number of mix-servers learn any information beyond the query result.
Further, if the querier is not corrupted, the corrupted mix-servers do not even learn the query result. We first comprehensively formalise these security properties of traceable mixnets and then propose a construction of traceable mixnets using novel
distributed zero-knowledge proofs (ZKPs) of set membership and of a statement we call reverse set membership. Although set membership has been studied in the single-prover setting, the main challenge in our distributed setting lies in making sure that
none of the mix-servers learn the association between ciphertexts and plaintexts during the proof. We implement our distributed ZKPs and show that they are faster than state-of-the-art by at least one order of magnitude.



## 2023/1943

* Title: Distinguisher and Related-Key Attack on HALFLOOP-96
* Authors: Jinpeng Liu, Ling Sun
* [Permalink](https://eprint.iacr.org/2023/1943)
* [Download](https://eprint.iacr.org/2023/1943.pdf)

### Abstract

HALFLOOP-96 is a 96-bit tweakable block cipher used in high frequency radio to secure automatic link establishment messages. In this paper, we concentrate on its differential properties in the contexts of conventional, related-tweak, and related-key
differential attacks. Using automatic techniques, we determine the minimum number of active S-boxes and the maximum differential probability in each of the three configurations. The resistance of HALFLOOP-96 to differential attacks in the conventional
and related-tweak configurations is good, and the longest distinguishers in both configurations consist of five rounds. In contrast, the security of the cipher against differential attacks in the related-key configuration is inadequate. The most
effective related-key distinguisher we can find spans eight rounds. The 8-round related-key differential distinguisher is then utilised to initiate a 9-round weak-key attack. With $2^{92.96}$ chosen-plaintexts, 38.77-bit equivalent information about the
keys can be recovered. Even though the attack does not pose a significant security threat to HALFLOOP-96, its security margin in the related-key configuration is exceedingly narrow. Therefore, improper use must be avoided in the application.



## 2023/1944

* Title: Revisiting The Multiple of Property for SKINNY The Exact Computation of the number of right pairs
* Authors: Hanbeom Shin, Insung Kim, Sunyeop Kim, Seonggyeom Kim, Deukjo Hong, Jaechul Sung, Seokhie Hong
* [Permalink](https://eprint.iacr.org/2023/1944)
* [Download](https://eprint.iacr.org/2023/1944.pdf)

### Abstract

At EUROCRYPT 2017, Grassi et al. proposed the multiple-of-8 property for 5-round AES, where the number $n$ of right pairs is a multiple of 8. At ToSC 2019, Boura et al. generalized the multiple-of property for a general SPN block cipher and applied it to
block cipher SKINNY.

In this paper, we present that $n$ is not only a multiple but also a fixed value for SKINNY. Unlike the previous proof of generalization of multiple-of property using equivalence class, we investigate the propagation of the set to compute the exact
number $n$. We experimentally verified that presented property holds. We extend this property one round more using the lack of the whitening key on the SKINNY and use this property to construct 6-round distinguisher on SKINNY-64 and SKINNY-128. The
probability of success of both distinguisher is almost 1 and the total complexities are $2^{16}$ and $2^{32}$ respectively. We verified that this property only holds for SKINNY, not for AES and MIDORI, and provide the conditions under which it exists for
AES-like ciphers.



## 2023/1945

* Title: The Fiat--Shamir Transformation of $(\Gamma_1,\dots,\Gamma_\mu)$-Special-Sound Interactive Proofs
* Authors: Thomas Attema, Serge Fehr, Michael Klooß, Nicolas Resch
* [Permalink](https://eprint.iacr.org/2023/1945)
* [Download](https://eprint.iacr.org/2023/1945.pdf)

### Abstract

The Fiat-Shamir transformation is a general principle to turn any public-coin interactive proof into non-interactive one (with security then typically analyzed in the random oracle model). While initially used for 3-round protocols, many recent
constructions use it for multi-round protocols. However, in general the soundness error of the Fiat-Shamir transformed protocol degrades exponentially in the number of rounds. On the positive side, it was shown that for the special class of $(k_1,\dots,k_
\mu)$-special-sound protocols the loss is actually only linear in the number of random oracle queries, and independent of the number of rounds, which is optimal.

A natural next question is whether this positive result extends to the Fiat-Shamir transformation of so-called $(\Gamma_1,\dots,\Gamma_\mu)$-special-sound protocols, a notion recently defined and analyzed in the interactive case, with the aim to capture
the most general notion of special-soundness.

We show in this work that this is indeed the case. Concretely, we show that the Fiat--Shamir transformation of any $(\Gamma_1,\dots,\Gamma_\mu)$-special-sound interactive proof is knowledge sound under the same condition under which the original
interactive proof is knowledge sound. Furthermore, also here the loss is linear in the number of random-oracle queries and independent of the number of rounds.

In light of the above, one might suspect that our argument follows as a straightforward combination of the above mentioned prior works. However, this is not the case. The approach used for $(k_1,\dots,k_\mu)$-special-sound protocols, which is based on an
extractor that samples without replacement, does not (seem to) generalize; on the other hand, the other approach, which uses an extractor based on sampling with replacement, comes with an additional loss that would blow up in the recursive multi-round
analysis.



## 2023/1946

* Title: SnarkFold: Efficient SNARK Proof Aggregation from Split Incrementally Verifiable Computation
* Authors: Xun Liu, Shang Gao, Tianyu Zheng, Bin Xiao
* [Permalink](https://eprint.iacr.org/2023/1946)
* [Download](https://eprint.iacr.org/2023/1946.pdf)

### Abstract

The succinct non-interactive argument of knowledge (SNARK) technique is widely used in blockchain systems to replace the costly on-chain computation with the verification of a succinct proof. However, when dealing with multiple proofs, most existing
applications require each proof to be independently verified, resulting in a heavy load on nodes and high transaction fees for users. To improve the efficiency of verifying multiple proofs, we introduce SnarkFold, a universal SNARK-proof aggregation
scheme based on incrementally verifiable computation (IVC). Unlike previous proof aggregation approaches based on inner product arguments, which have a logarithmic proof size and verification cost, SnarkFold achieves constant verification time and proof
size. One core technical advance in SnarkFold, of independent interest, is the ``split IVC'': rather than using one running instance to fold/accumulate the computation, we employ two (or more) running instances of different types in the recursive circuit
to avoid transferring into the same structure. This distinguishing feature is particularly well-suited for proof aggregation scenarios, as constructing arithmetic circuits for pairings can be expensive. We further demonstrate how to fold Groth16 proofs
with our SnarkFold. With some further optimizations, SnarkFold achieves the highest efficiency among all approaches.



## 2023/1947

* Title: Using Predicate Extension for Predicate Encryption to Generically Obtain Chosen-Ciphertext Security and Signatures
* Authors: Marloes Venema, Leon Botros
* [Permalink](https://eprint.iacr.org/2023/1947)
* [Download](https://eprint.iacr.org/2023/1947.pdf)

### Abstract

Predicate encryption (PE) is a type of public-key encryption that captures many useful primitives such as attribute-based encryption (ABE). Although much progress has been made to generically achieve security against chosen-plaintext attacks (CPA)
efficiently, in practice, we also require security against chosen-ciphertext attacks (CCA). Because achieving CCA-security on a case-by-case basis is a complicated task, several generic conversion methods have been proposed, which typically target
different subclasses of PE such as ciphertext-policy ABE. As is common, such conversion methods may sacrifice some efficiency. Notably, for ciphertext-policy ABE, all proposed generic transformations incur a significant decryption overhead. Furthermore,
depending on the setting in which PE is used, we may also want to require that messages are signed. To do this, predicate signature schemes can be used. However, such schemes provide a strong notion of privacy for the signer, which may be stronger than
necessary for some practical settings at the cost of efficiency.

In this work, we propose the notion of predicate extension, which transforms the predicate used in a PE scheme to include one additional attribute, in both the keys and the ciphertexts. Using predicate extension, we can generically obtain CCA-security
and signatures from a CPA-secure PE scheme. For the CCA-security transform, we observe that predicate extension implies a two-step approach to achieving CCA-security. This insight broadens the applicability of existing transforms for specific subclasses
of PE to cover all PE. We also propose a new transform that incurs slightly less overhead than existing transforms. Furthermore, we show that predicate extension allows us to create a new type of signatures, which we call PE-based signatures. PE-based
signatures are weaker than typical predicate signatures in the sense that they do not provide privacy for the signer. Nevertheless, such signatures may be more suitable for some practical settings owing to their efficiency or reduced interactivity.
Lastly, to show that predicate extensions may facilitate a more efficient way to achieve CCA-security generically than existing methods, we propose a novel predicate-extension transformation for a large class of pairing-based PE, covered by the pair and
predicate encodings frameworks. In particular, this yields the most efficient generic CCA-conversion for ciphertext-policy ABE.



## 2023/1948

* Title: PriDe CT: Towards Public Consensus, Private Transactions, and Forward Secrecy in Decentralized Payments
* Authors: Yue Guo, Harish Karthikeyan, Antigoni Polychroniadou
* [Permalink](https://eprint.iacr.org/2023/1948)
* [Download](https://eprint.iacr.org/2023/1948.pdf)

### Abstract

Anonymous Zether, proposed by Bunz et al. (FC, 2020) and subsequently improved by Diamond (IEEE S&P, 2021) is an account-based confidential payment mechanism that works by using a smart contract to achieve privacy (i.e. identity of receivers to
transactions and payloads are hidden). In this work, we look at simplifying the existing protocol while also achieving batching of transactions for multiple receivers, while ensuring consensus and forward secrecy. To the best of our knowledge, this work
is the first to formally study the notion of forward secrecy in the setting of blockchain, borrowing a very popular and useful idea from the world of secure messaging. Specifically, we introduce:
- FUL-Zether, a forward-secure version of Zether (Bunz et al., FC, 2020).
- PRIvate DEcentralized Confidental Transactions (PriDe CT), a much-simplified version of Anonymous Zether that achieves competitive performance and enables batching of transactions for multiple receivers.
- PRIvate DEcentralized Forward-secure Until Last update
Confidential Transactions (PriDeFUL CT), a forward-secure version of PriDe CT. We also present an open-source, Ethereum-based implementation of our system. PriDe CT uses linear homomorphic encryption as Anonymous Zether but with simpler zero-knowledge proofs. PriDeFUL CT uses an updatable public key encryption scheme to achieve forward secrecy by introducing a new DDH-based construction in the standard
model.
In terms of transaction sizes, Quisquis (Asiacrypt, 2019), which is the only cryptocurrency that supports batchability (albeit in the UTXO model), has 15 times more group elements than PriDe CT. Meanwhile, for a ring of $N$ receivers, Anonymous Zether
requires $6\log N$ more terms even without accounting for the ability to batch in PriDe CT. Further, our implementation indicates that, for $N=32$, even if there were 7 intended receivers, PriDe CT outperforms Anonymous Zether in proving time and gas
consumption.



## 2023/1949

* Title: HELIOPOLIS: Verifiable Computation over Homomorphically Encrypted Data from Interactive Oracle Proofs is Practical
* Authors: Diego F. Aranha, Anamaria Costache, Antonio Guimarães, Eduardo Soria-Vazquez
* [Permalink](https://eprint.iacr.org/2023/1949)
* [Download](https://eprint.iacr.org/2023/1949.pdf)

### Abstract

Homomorphic encryption (HE) enables computation on encrypted data, which in turn facilitates the outsourcing of computation on private data. However, HE offers no guarantee that the returned result was honestly computed by the cloud. In order to have
such guarantee, it is necessary to add verifiable computation (VC) into the system.

The most efficient recent works in VC over HE focus on verifying operations on the ciphertext space of the HE scheme, which usually lacks the algebraic structure that would make it compatible with existing VC systems. For example, multiplication of
ciphertexts in the current most efficient HE schemes requires non-algebraic operations such as real division and rounding. Therefore, existing works for VC over HE have to either give up on those efficient HE schemes, or incur a large overhead (an amount
of constraints proportional to the ciphertext ring's size) in order to emulate these non-algebraic operations.

In this work, we move away from that paradigm by placing the verification checks in the plaintext space of HE, all while the prover remains computing on ciphertexts. We achieve this by introducing a general transformation for Interactive Oracle Proofs (
IOPs) to work over HE, whose result we denote as HE-IOPs. We apply this same transformation to the FRI [Ben-Sasson et al., ICALP 2018] IOP of proximity and we show how to compile HE-Reed Solomon-encoded IOPs and HE-$\delta$-correlated-IOPs with HE-FRI
into HE-IOPs.

Furthermore, our construction is compatible with a prover that provides input in zero-knowledge, and only relies on building blocks
that are plausibly quantum-safe.

Aligning the security parameters of HE and FRI is a difficult task for which we introduce several optimizations. We demonstrate their efficiency with a proof-of-concept implementation in Python and show that, for an encrypted Reed Solomon codeword with
degree bound $2^{11}$ and rate $1/16$ in a (plaintext) field of size $2^{256}$, we can run FRI's commit phase in just 43 minutes on a single thread on a c6i.metal instance (which could be reduced to less than a minute in a multi-threaded implementation
in a large server). Verification takes less than 0.2 seconds, and, based on micro-benchmarks of the employed techniques, we show it could be up to 100 times faster in a fully optimized implementation.



## 2023/1950

* Title: GigaDORAM: Breaking the Billion Address Barrier
* Authors: Brett Falk, Rafail Ostrovsky, Matan Shtepel, Jacob Zhang
* [Permalink](https://eprint.iacr.org/2023/1950)
* [Download](https://eprint.iacr.org/2023/1950.pdf)

### Abstract

We design and implement GigaDORAM, a novel
3-server Distributed Oblivious Random Access Memory (DORAM) protocol. Oblivious RAM allows a client to read and write to memory on an untrusted server while ensuring the server itself learns nothing about the client's access pattern. Distributed
Oblivious RAM (DORAM) allows a group of servers to efficiently access a secret-shared array at a secret-shared index.

A recent generation of DORAM implementations (e.g. FLORAM, DuORAM) has focused on building DORAM protocols based on Function Secret-Sharing (FSS). These protocols have low communication complexity and low round complexity but linear computational
complexity of the servers. Thus, they work for moderate-size databases, but at a certain size, these FSS-based protocols become computationally inefficient.

In this work, we introduce GigaDORAM, a hierarchical-solution-based DORAM featuring poly-logarithmic computation and communication, but with an over $100\times$ reduction in rounds per query compared to previous hierarchical DORAM protocols. In our
implementation, we show that for moderate to large databases where FSS-based solutions become computation-bound, our protocol is orders of magnitude more efficient than the best existing DORAM protocols. When $N = 2^{31}$, our DORAM is able to perform
over 700 queries per second.

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