## In this issue

1. [2023/1392] Robust Publicly Verifiable Covert Security: Limited ...
2. [2023/1724] Accountability for Misbehavior in Threshold ...
3. [2023/1973] Combinatorially Homomorphic Encryption
4. [2024/1] On short digital signatures with Eulerian ...
5. [2024/2] Fast polynomial multiplication using matrix ...
6. [2024/3] Simple Soundness Proofs
7. [2024/4] Practical Two-party Computational Differential ...
8. [2024/5] The Multiple Millionaires’ Problem
9. [2024/6] Towards general-purpose program obfuscation via ...
10. [2024/7] Password Protected Universal Thresholdizer
11. [2024/8] SoK: Methods for Sampling Random Permutations in ...
12. [2024/9] Distributed Protocols for Oblivious Transfer and ...
13. [2024/10] On the tropical two-sided discrete logarithm and a ...
14. [2024/11] MetaDORAM: Breaking the Log-Overhead Information ...
15. [2024/12] Two-Round ID-PAKE with strong PFS and single ...
16. [2024/13] A note on ``intelligent drone-assisted robust ...
17. [2024/14] A Lattice-based Accountable Subgroup Multi- ...
18. [2024/15] Unconditionally secure MPC for Boolean circuits ...
19. [2024/16] Reducing the computational complexity of fuzzy ...
20. [2024/17] PT-symmetric mapping of three states and its ...

## 2023/1392

* Title: Robust Publicly Verifiable Covert Security: Limited Information Leakage and Guaranteed Correctness with Low Overhead
* Authors: Yi Liu, Junzuo Lai, Qi Wang, Xianrui Qin, Anjia Yang, Jian Weng
* [Permalink](https://eprint.iacr.org/2023/1392)
* [Download](https://eprint.iacr.org/2023/1392.pdf)

### Abstract

Protocols with \emph{publicly verifiable covert (PVC) security} offer high efficiency and an appealing feature: a covert party may deviate from the protocol, but with a probability (\eg $90\%$, referred to as the \emph{deterrence factor}), the honest party can identify this deviation and expose it using a publicly verifiable certificate. These protocols are particularly suitable for practical applications involving reputation-conscious parties.

However, in the cases where misbehavior goes undetected (\eg with a probability of $10\%$), \emph{no security guarantee is provided for the honest party}, potentially resulting in a complete loss of input privacy and output correctness.

In this paper, we tackle this critical problem by presenting a highly effective solution. We introduce and formally define an enhanced notion called \emph{robust PVC security}, such that even if the misbehavior remains undetected, the malicious party can only gain an additional $1$-bit of information about the honest party's input while maintaining the correctness of the output. We propose a novel approach leveraging \emph{dual execution} and \emph{time-lock puzzles} to design a robust PVC-secure two-party protocol with \emph{low overhead} (depending on the deterrence factor). For instance, with a deterrence factor of $90\%$, our robust PVC-secure protocol incurs \emph{only additional ${\sim}10\%$ overhead} compared to the state-of-the-art PVC-secure protocol.

Given the stronger security guarantees with low overhead, our protocol is highly suitable for practical applications of secure two-party computation.

## 2023/1724

* Title: Accountability for Misbehavior in Threshold Decryption via Threshold Traitor Tracing
* Authors: Dan Boneh, Aditi Partap, Lior Rotem
* [Permalink](https://eprint.iacr.org/2023/1724)
* [Download](https://eprint.iacr.org/2023/1724.pdf)

### Abstract

A $t$-out-of-$n$ threshold decryption system assigns key shares to $n$ parties so that any $t$ of them can decrypt a well-formed ciphertext. Existing threshold decryption systems are not secure when these parties are rational actors: an adversary can offer to pay the parties for their key shares. The problem is that a quorum of $t$ parties, working together, can sell the adversary a decryption key that reveals nothing about the identity of the traitor parties. This provides a risk-free profit for the parties since there is no accountability for their misbehavior --- the information they sell to the adversary reveals nothing about their identity. This behavior can result in a complete break in many applications of threshold decryption, such as encrypted mempools, private voting, and sealed-bid auctions.

In this work we show how to add accountability to threshold decryption systems to deter this type of risk-free misbehavior. Suppose a quorum of $t$ or more parties construct a decoder algorithm $D(\cdot)$ that takes as input a ciphertext and outputs the corresponding plaintext or $\bot$. They sell $D$ to the adversary. Our threshold decryption systems are equipped with a tracing algorithm that can trace $D$ to members of the quorum that created it. The tracing algorithm is only given blackbox access to $D$ and will identify some members of the misbehaving quorum. The parties can then be held accountable, which may discourage them from selling the decoder $D$ in the first place.

Our starting point is standard (non-threshold) traitor tracing, where $n$ parties each holds a secret key. Every party can decrypt a well-formed ciphertext on its own. However, if a subset of parties ${\cal J} \subseteq [n]$ collude to create a pirate decoder $D(\cdot)$ that can decrypt well-formed ciphertexts, then it is possible to trace $D$ to at least one member of ${\cal J}$ using only blackbox access to the decoder $D$. Traitor tracing received much attention over the years and multiple schemes have been developed.

In this work we develop the theory of traitor tracing for threshold decryption, where now only a subset ${\cal J} \subseteq [n]$ of $t$ or more parties can collude to create a pirate decoder $D(\cdot)$. This problem has recently become quite important due to the real-world deployment of threshold decryption in encrypted mempools, as we explain in the paper. While there are several non-threshold traitor tracing schemes that we can leverage, adapting these constructions to the threshold decryption settings requires new cryptographic techniques. We present a number of constructions for traitor tracing for threshold decryption, and note that much work remains to explore the large design space.

## 2023/1973

* Title: Combinatorially Homomorphic Encryption
* Authors: Yuval Ishai, Eyal Kushnir, Ron D. Rothblum
* [Permalink](https://eprint.iacr.org/2023/1973)
* [Download](https://eprint.iacr.org/2023/1973.pdf)

### Abstract

Homomorphic encryption enables public computation over encrypted data. In the past few decades, homomorphic encryption has become a staple of both the theory and practice of cryptography. Nevertheless, while there is a general loose understanding of what it means for a scheme to be homomorphic, to date there is no single unifying minimal definition that captures all schemes.
In this work, we propose a new definition, which we refer to as combinatorially homomorphic encryption, which attempts to give a broad base that captures the intuitive meaning of homomorphic encryption and draws a clear line between trivial and nontrivial homomorphism.

Our notion relates the ability to accomplish some task when given a ciphertext, to accomplishing the same task without the ciphertext, in the context of communication complexity. Thus, we say that a scheme is combinatorially homomorphic if there exists a communication complexity problem $f(x,y)$ (where $x$ is Alice's input and $y$ is Bob's input) which requires communication $c$, but can be solved with communication less than $c$ when Alice is given in addition also an encryption $E_k(y)$ of Bob's input (using Bob's key $k$).

We show that this definition indeed captures pre-existing notions of homomorphic encryption and (suitable variants are) sufficiently strong to derive prior known implications of homomorphic encryption in a conceptually appealing way. These include constructions of (lossy) public-key encryption from homomorphic private-key encryption, as well as collision-resistant hash functions and private information retrieval schemes.

## 2024/1

* Title: On short digital signatures with Eulerian transformations
* Authors: Vasyl Ustimenko
* [Permalink](https://eprint.iacr.org/2024/001)
* [Download](https://eprint.iacr.org/2024/001.pdf)

### Abstract

Let n stands for the length of digital signatures with quadratic multivariate public rule in n variables. We construct postquantum secure procedure to sign O(n^t), t ≥1 digital documents with the signature of size n in time O(n^{3+t}). It allows to sign O(n^t), t <1 in time O(n^4). The procedure is defined in terms of Algebraic Cryptography. Its security rests on the semigroup based protocol of Noncommutative Cryptography referring to complexity of the decomposition of the collision element into composition into given generators. The protocol uses the semigroup of Eulerian transformations of variety (K*)^n where K* is a nontrivial multiplicative group of the finite commutative ring K. Its execution complexity is O(n^3). Additionally we use this protocol to define asymmetric cryptosystem with the space of plaintexts and ciphertexts (K*)^n which allows users to encrypt and decrypt O(n^t) documents of size n in time O(n^{3+[t]}) where [x] stands for the flow function from x. Finally we suggest protocol based cryptosystem working with plaintext space (K*)^n and the space of ciphertext K^n which allows decryption of O(n^t), t>1 documents of size n in time O(n^{t+3}), t>1. The multivariate encryption map has linear degree O(n) and density O(n^4). We discuss the idea of public key with Eulerian transformations which allows to sign O(n^t), t≥0 documents in time O(n^{t+2}). The idea of delivery and usage of several Eulerian and quadratic transformations is also discussed.