# NordiCrypt Spring 2023

# Important information

On the 23rd of March DTU will hold the first NordiCrypt meetup at DTU Lyngby in Copenhagen in Meeting Room S12 in Building 101. The program can be found below.

Registration is free and drinks and lunch are included, although you'll have to pay for the dinner yourself. If you want to attend, please send an e-mail to Carsten Baum until the 16th of March. Please also indicate in the e-mail if you want to attend the dinner.

# Program

### 10:55-11:00 Welcome

### 11:00 - 11:25 Anders Konring (ITU): Perfect MPC over Layered Graphs

The classical "BGW protocol" (Ben-Or, Goldwasser and Wigderson, STOC 1988) shows that secure multiparty computation (MPC) among parties can be realized with perfect full security if t<n/3 parties are corrupted. This holds against malicious adversaries in the "standard" model for MPC, where a fixed set of n parties is involved in the full execution of the protocol.

However, the picture is less clear in the mobile adversary setting of Ostrovsky and Yung (PODC 1991), where the adversary may periodically "move" by uncorrupting parties and corrupting a new set of t parties. In this setting, it is unclear if full security can be achieved against an adversary that is maximally mobile, i.e., moves after every round. The question is further motivated by the "You Only Speak Once" (YOSO) setting of Gentry et al. (Crypto 2021), where not only the adversary is mobile but also each round is executed by a disjoint set of parties. Previous positive results in this model do not achieve perfect security, and either assume probabilistic corruption and a nonstandard communication model, or only realize the weaker goal of security-with-abort. The question of matching the BGW result in these settings remained open.

In this work, we tackle the above two challenges simultaneously. We consider a layered MPC model, a simplified variant of the fluid MPC model of Choudhuri et al. (Crypto 2021). Layered MPC is an instance of standard MPC where the interaction pattern is defined by a layered graph of width n, allowing each party to send secret messages and broadcast messages only to parties in the next layer. We require perfect security against a malicious adversary who may corrupt at most t parties in each layer.

Our main result is a perfect, fully secure layered MPC protocol with an optimal corruption threshold of t<n/3, thus extending the BGW feasibility result to the layered setting. This implies perfectly secure MPC protocols against a maximally mobile adversary.

### 11:30 - 11:55 Damiano Abram (AU): A story about removing trusted setups in one round

A distributed sampler is a way for several mutually distrusting parties to non-interactively generate a common reference string (CRS) that all parties trust. The talk summarises the results of three works on the topic.

In the first one (Eurocrypt 2022), leveraging indistinguishability obfuscation, we showed how to construct semi-honest distributed samplers in the plain model. By relying on a programmable random oracle, we upgraded the construction to active security.

In the second work, we proved that actively secure distributed samplers need random oracles and the CRS model does not help in obtaining efficient constructions. Formally, we proved that any actively secure construction relies on a long, non-reusable CRS that cannot be unstructured.

In the final work, we got around the impossibility by moving from a simulation-based definition to a game-based definition. In particular, our notion implies that the hardness of a wide range of security games is preserved when the CRS is replaced with a distributed sampler.

The works are the result of collaborations with various coauthors: Maciej Obremski, Peter Scholl, Brent Waters, Sophia Yakoubov and Mark Zhandry.

### 12:00 - 13:00 Lunch break

### 13:00 - 13:25 Rasmus Pagh (KU): Distributed Differential Privacy using Tools from Cryptography

Differential privacy was originally studied in the setting where there is a trusted entity, a “curator”, that would receive all data and release statistics that satisfy differential privacy. In principle, this setup can be simulated without a trusted entity using general-purpose multi-party computation, but this approach is often not practical. An alternative is that each data owner releases a “local” differentially private digest of its data, but for many problems of interest this can only be used to compute very noisy answers, and is not practical for that reason. During the last 5 years there has been a large interest in using “lightweight” cryptographic primitives such as mixnets as a basis for distributed, differentially private protocols. The talk will briefly introduce differential privacy and give a high-level overview of these developments, focusing particularly on the “shuffle model” of differential privacy.

### 13:30 - 13:55 Tyge Tiessen (DTU): How likely are Boomerangs to return?

Boomerang attacks are a cryptanalytic tool built on differential cryptanalysis. They can both be used to distinguish insecure block ciphers from random permutations as well as to recover the key. We will take a closer look into difficulties arising when estimating the success probabilities of these attacks.

### 14:00 - 14:25 Lorenzo (ITU): PAPR: Publicly Auditable Privacy Revocation for Anonymous Credentials

In the presented paper (appearing soon at CT-RSA 2023), we study the notion of anonymous credentials with Publicly Auditable Privacy Revocation (PAPR). PAPR credentials simultaneously provide conditional user privacy and auditable privacy revocation. The first property implies that users keep their identity private when authenticating unless and until an appointed authority requests to revoke this privacy, retroactively. The second property enforces that auditors can verify whether or not this authority has revoked privacy from an issued credential (i.e. learned the identity of the user who owns that credential), holding the authority accountable. In other words, the second property enriches conditionally anonymous credential systems with transparency by design, effectively discouraging such systems from being used for mass surveillance. In this work, we introduce the notion of a PAPR anonymous credential scheme, formalize it as an ideal functionality, and present constructions that are provably secure under standard assumptions in the Universal Composability framework. The core tool in our PAPR construction is a mechanism for randomly selecting an anonymous committee which users secret share their identity information towards, while hiding the identities of the committee members from the authority. As a consequence, in order to initiate the revocation process for a given credential, the authority is forced to post a request on a public bulletin board used as a broadcast channel to contact the anonymous committee that holds the keys needed to decrypt the identity connected to the credential. This mechanism makes the user de-anonymization publicly auditable.

### 15:00 - 15:30 Coffee break

### 15:30 - 15:55 Freja Elbro (DTU): An Algebraic Attack Against McEliece-like Cryptosystems Based on BCH Codes

We present an algebraic attack on a McEliece-like scheme based on BCH codes (BCH-McEliece), where the Goppa code is replaced by a suitably permuted BCH code. Our attack continues the line of work devising attacks against McEliece-like schemes with Goppa-like codes, with the goal of getting a better understanding of why Goppa codes are so intractable. Our starting point is the work of Faugère, Perret and Portzamparc (Asiacrypt 2014). We take their algebraic model and adapt and improve their attack algorithm so that it can handle BCH-McEliece. We implement the attack and exhibit a parameter range where our attack is practical while generic attacks suggest cryptographic security.

### 16:00 - 16:25 Peter Scholl (AU): Oblivious Transfer with Constant Computational Overhead

### 19:00 - open end: Dinner

At Restaurant Capeesh in Copenhagen. If you want to join, please contact Luisa Siniscalchi.

# Location

To attend the event from outside of DTU, take the 150S or 15E bus from Nørreport Station in Copenhagen to Rævehøjvej, DTU. From the bus stop, it is a 5min walk to the 101 building.

If you come from Aarhus and your train does not go directly to Nørreport Station, you can either take any S-Tog from Copenhagen Central Station for 2 stops or take the A or E S-Tog directly from the central station to Lyngby Station. From there, the bus 300S gets you in a few minutes to DTU Building 101.