## In this issue

1. [2023/206] Orca: FSS-based Secure Training with GPUs
2. [2023/558] A Multireceiver Certificateless Signcryption (MCLS) ...
3. [2023/1406] Sigmabus: Binding Sigmas in Circuits for Fast Curve ...
4. [2023/1407] Fully Homomorphic Encryption-Based Protocols for ...
5. [2023/1464] Round-Robin is Optimal: Lower Bounds for Group ...
6. [2023/1465] Too Close for Comfort? Measuring Success of ...
7. [2023/1466] On Black-Box Verifiable Outsourcing
8. [2023/1467] GPU Acceleration of High-Precision Homomorphic ...
9. [2023/1468] QFESTA: Efficient Algorithms and Parameters for ...
10. [2023/1469] SLAP: Succinct Lattice-Based Polynomial Commitments ...
11. [2023/1470] Zero-Knowledge Systems from MPC-in-the-Head and ...
12. [2023/1471] NTRU in Quaternion Algebras of Bounded Discriminant
13. [2023/1472] Naysayer proofs
14. [2023/1473] Cicada: A framework for private non-interactive on- ...
15. [2023/1474] Mitigation on the AIM Cryptanalysis
16. [2023/1475] Tropical cryptography III: digital signatures
17. [2023/1476] Auditable Obfuscation
18. [2023/1477] G+G: A Fiat-Shamir Lattice Signature Based on ...
19. [2023/1478] Succinct Proofs and Linear Algebra
20. [2023/1479] Rational Broadcast Protocols against Timid Adversaries
21. [2023/1480] The Pre-Shared Key Modes of HPKE

## 2023/206

* Title: Orca: FSS-based Secure Training with GPUs
* Authors: Neha Jawalkar, Kanav Gupta, Arkaprava Basu, Nishanth Chandran, Divya Gupta, Rahul Sharma
* [Permalink](https://eprint.iacr.org/2023/206)
* [Download](https://eprint.iacr.org/2023/206.pdf)

### Abstract

Secure Two-party Computation (2PC) allows two parties to compute any function on their private inputs without revealing their inputs to each other. In the offline/online model for 2PC, correlated randomness that is independent of all inputs to the computation, is generated in a preprocessing (offline) phase and this randomness is then utilized in the online phase once the inputs to the parties become available. Most 2PC works focus on optimizing the online time as this overhead lies on the critical path. A recent paradigm for obtaining efficient 2PC protocols with low online cost is based on the cryptographic technique of function secret sharing (FSS).
We build an end-to-end system ORCA to accelerate the computation of FSS-based 2PC protocols with GPUs. Next, we observe that the main performance bottleneck in such accelerated protocols is in storage (due to the large amount of correlated randomness), and we design new FSS-based 2PC protocols for several key functionalities in ML which reduce storage by up to 5×. Compared to prior state-of-the-art on secure training accelerated with GPUs in the same computation model (PIRANHA, Usenix Security 2022), we show that ORCA has 4% higher accuracy, 98× lesser communication, and is 26× faster on CIFAR-10. Moreover, maintaining training accuracy while using fixed-point needs stochastic truncations, and all prior works on secure fixed-point training (including PIRANHA) use insecure protocols for it. We provide the first secure protocol for stochastic truncations and build on it to provide the first evaluation of training with end-to-end security. For secure ImageNet inference, ORCA achieves sub-second latency for VGG-16 and ResNet-50, and outperforms the state-of-the-art by 8 − 103×.

## 2023/558

* Title: A Multireceiver Certificateless Signcryption (MCLS) Scheme
* Authors: Alia Umrani, Apurva K Vangujar, Paolo Palmieri
* [Permalink](https://eprint.iacr.org/2023/558)
* [Download](https://eprint.iacr.org/2023/558.pdf)

### Abstract

User authentication and message confidentiality are the basic security requirements of high-end applications such as multicast communication and distributed systems. Several efficient signature-then-encrypt cryptographic schemes have been proposed to offer these security requirements with lower computational cost and communication overhead. However, signature-then-encryption techniques take more computation time than signcryption techniques. Signcryption accomplishes both digital signature and public key encryption functions in a single logical step and at a much lower cost than ``signature followed by encryption.'' Several signcryption schemes based on bilinear pairing operations have been proposed. Similarly, anonymous multi-receiver encryption has recently risen in prominence in multicast communication and distributed settings, where the same messages are sent to several receivers but the identity of each receiver should remain private. Anonymous multi-receiver encryption allows a receiver to obtain the plaintext by decrypting the ciphertext using their own private key, while their identity is kept secret to anyone, including other receivers. Among the Certificateless Multi-receiver Encryption (CLMRE) schemes that have been introduced, Hung et al. proposed an efficient Anonymous Multireceiver Certificateless Encryption (AMCLE) scheme ensuring confidentiality and anonymity based on bilinear pairings and is secure against IND-CCA and ANON-CCA.

In this paper, we substantially extend Hung et al.’s multireceiver certificateless encryption scheme to a Multireceiver Certificateless Signcryption (MCLS) scheme that provides confidentiality along with authentication. We show that, as compared to Hung et al.’s encryption scheme, our signcryption scheme requires only three additional multiplication operations for signcryption and unsigncryption phases. Whereas, the signcryption cost is linear with the number of designated receivers while the unsigncryption cost remains constant for each designated receiver. We compare the results with other existing single receiver and multireceiver signcryption schemes in terms of number of operations, exemption of key escrow problem, and public key settings. The scheme proposed in this paper is more efficient for single and multireceiver signcryption schemes while providing exemption from the key escrow problem, and working in certificateless public key settings.

## 2023/1406

* Title: Sigmabus: Binding Sigmas in Circuits for Fast Curve Operations
* Authors: George Kadianakis, Mary Maller, Andrija Novakovic
* [Permalink](https://eprint.iacr.org/2023/1406)
* [Download](https://eprint.iacr.org/2023/1406.pdf)

### Abstract

This paper introduces Sigmabus, a technique designed to enhance the efficiency of zero-knowledge circuits by relocating computationally expensive operations outside the circuit. Specifically, Sigmabus focuses on moving elliptic curve group operations, typically proven with expensive non-native field arithmetic, to external computations. By leveraging Sigma protocols, elliptic curve group operations are proven outside the circuit, while additional constraints are applied to the circuit to ensure correct execution of the Sigma protocol.. This approach can achieve significant performance improvements in zero-knowledge circuits. This paper presents the Sigmabus protocol along with its security proofs, and demonstrates its practical implications through various use cases.

## 2023/1407

* Title: Fully Homomorphic Encryption-Based Protocols for Enhanced Private Set Intersection Functionalities
* Authors: JINGWEI HU, Junyan Chen, Wangchen Dai, Huaxiong Wang
* [Permalink](https://eprint.iacr.org/2023/1407)
* [Download](https://eprint.iacr.org/2023/1407.pdf)

### Abstract

This study delves into secure computations for set intersections using fully homomorphic encryption (FHE) within the semi-honest setting. Our protocols facilitate joint computations between two parties, each holding a set of inputs denoted as $N_s$ and $N_r$ in size, respectively. The primary objective is to determine various functionalities, such as intersection size and sum, while maintaining data confidentiality. These functionalities extend the classic private set intersection (PSI) and have practical applications in contact tracing, ad conversion analysis, and online dating, each abstracted into specialized PSI protocols.

Our work demonstrates that these extended PSI functionalities are interconnected, with the PSI-cardinality protocol serving as the foundation. By adapting this protocol, we naturally arrive at PSI-sum-cardinality. Additionally, PSI-token-threshold is achieved by augmenting PSI-cardinality with FHE-based oblivious polynomial evaluation (OPE). The tPSI protocol combines PSI-token-threshold and standard PSI, allowing information sharing when the intersection size exceeds a threshold.

Our protocols excel in simplicity, enhancing ease of understanding, implementation, optimization, and long-term maintenance. They also exhibit sublinear communication complexity concerning the larger sender's set, rendering them well-suited for scenarios involving substantial data. Various optimization techniques further bolster their practical efficiency.

## 2023/1464

* Title: Round-Robin is Optimal: Lower Bounds for Group Action Based Protocols
* Authors: Daniele Cozzo, Emanuele Giunta
* [Permalink](https://eprint.iacr.org/2023/1464)
* [Download](https://eprint.iacr.org/2023/1464.pdf)

### Abstract

An hard homogeneous space (HHS) is a finite group acting on a set with
the group action being hard to invert and the set lacking any algebraic
structure.
As such HHS could potentially replace finite groups where the discrete logarithm is hard for building cryptographic primitives and protocols in a post-quantum world.

Threshold HHS-based primitives typically require parties to compute the group action of a secret-shared input on a public set element.
On one hand this could be done through generic MPC techniques, although they incur in prohibitive costs due to the high complexity of circuits evaluating group actions known to date.
On the other hand round-robin protocols only require black box usage of the HHS.
However these are highly sequential procedures, taking as many rounds as parties involved.
The high round complexity appears to be inherent due the lack of homomorphic properties in HHS, yet no lower bounds were known so far.