## IACR News

Here you can see all recent updates to the IACR webpage. These updates are also available:

#### 12 January 2021

###### Pedro Hecht

ePrint Report#### 07 January 2021

###### Microsoft Research, Redmond, WA

Job PostingThe Cryptography and Privacy Research Group at Microsoft Research, Redmond, is looking for candidates for Researcher positions.

Topics of particular interest to us include (but are not limited to) secure computing (FHE, MPC, TEE), ML privacy, end-to-end encryption, web privacy and security, post-quantum cryptography, and zero-knowledge proofs. Our work ranges from protocol design and security analysis to cryptography and privacy engineering, so we encourage people with any relevant experiences to apply.

**Responsibilities:**
Working with other researchers and multi-disciplinary teams to create and build practical solutions to real-world privacy problems.
Publishing papers in academic conferences.

**Required Qualifications:**

- A PhD (or close to completion) in computer science, electrical engineering, mathematics, or a related field
- Publications in top conferences, or submitted/accepted papers in top journals.

**Apply:** https://careers.microsoft.com/us/en/job/953748/Researcher-Cryptography-and-Privacy-Microsoft-Research

**Closing date for applications:**

**Contact:** Kim Laine, Melissa Chase, or Esha Ghosh

**More information:** https://careers.microsoft.com/us/en/job/953748/Researcher-Cryptography-and-Privacy-Microsoft-Research

###### Microsoft Research, Redmond, WA

Job PostingThe Cryptography and Privacy Research Group at Microsoft Research, Redmond, is looking for candidates for Post-Doc Researcher positions.

Topics of particular interest to us include (but are not limited to) secure computing (FHE, MPC, TEE), ML privacy, end-to-end encryption, web privacy and security, post-quantum cryptography, and zero-knowledge proofs. Our work ranges from protocol design and security analysis to cryptography and privacy engineering, so we encourage people with any relevant experiences to apply.

**Responsibilities:**
Working with other researchers and multi-disciplinary teams to create and build practical solutions to real-world privacy problems.
Publishing papers in academic conferences.

**Required Qualifications:**
A PhD (or close to completion) in computer science, electrical engineering, mathematics, or a related field
Publications in top conferences, or submitted/accepted papers in top journals.

**Apply:** https://careers.microsoft.com/us/en/job/953746/Post-Doc-Researcher-Cryptography-and-Privacy-Microsoft-Research

**Closing date for applications:**

**Contact:** Kim Laine, Melissa Chase, or Esha Ghosh

**More information:** https://careers.microsoft.com/us/en/job/953746/Post-Doc-Researcher-Cryptography-and-Privacy-Microsoft-Research

###### KU Leuven COSIC, Belgium

Job Posting**Closing date for applications:**

**Contact:** jobs-cosic@esat.kuleuven.be

**More information:** https://www.esat.kuleuven.be/cosic/vacancies/

###### KU Leuven COSIC

Job Posting**Closing date for applications:**

**Contact:** jobs-cosic@esat.kuleuven.be

**More information:** https://www.esat.kuleuven.be/cosic/vacancies/

#### 06 January 2021

###### Nicholas Stifter, Aljosha Judmayer, Philipp Schindler, Andreas Kern, Walid Fdhila

ePrint Report###### Patrick Derbez, Pierre-Alain Fouque

ePrint Report###### Patrick Derbez, Pierre-Alain Fouque, Victor Mollimard

ePrint Report###### Stéphanie Delaune, Patrick Derbez, Mathieu Vavrille

ePrint Report###### Kaushik Nath, Palash Sarkar

ePrint Report###### Yuhao Yang, Xiujie Huang

ePrint Report###### Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, Yuval Ishai

ePrint ReportOur protocols use two data-collection servers and, in a protocol run, each client send sends only a single message to the servers. Our protocols protect client privacy against arbitrary misbehavior by one of the servers and our approach requires no public- key cryptography (except for secure channels), nor general-purpose multiparty computation. Instead, we rely on incremental distributed point functions, a new cryptographic tool that allows a client to succinctly secret-share the labels on the nodes of an exponentially large binary tree, provided that the tree has a single non-zero path. Along the way, we develop new general tools for providing malicious security in applications of distributed point functions.

A limitation of our heavy-hitters protocol is that it reveals to the servers slightly more information than the set of popular strings itself. We precisely define and quantify this leakage and explain how to ameliorate its effects. In an experimental evaluation with two servers on opposite sides of the U.S., the servers can find the 200 most popular strings among a set of 400,000 client-held 256-bit strings in 54 minutes. Our protocols are highly parallelizable. We estimate that with 20 physical machines per logical server, our protocols could compute heavy hitters over ten million clients in just over one hour of computation.

###### Geoffroy Couteau, Pooya Farshim, Mohammad Mahmoody

ePrint ReportBy introducing and formalizing the notion of black-box uselessness, we develop a framework that allows us to make such conclusions. At an informal level, we call primitive $\mathcal{Q}$ black-box useless (BBU) for primitive $\mathcal{P}$ if $\mathcal{Q}$ cannot help constructing $\mathcal{P}$ in a black-box way, even in the presence of another primitive $\mathcal{Z}$. This is formalized by saying that $\mathcal{Q}$ is BBU for $\mathcal{P}$ if for any auxiliary primitive $\mathcal{Z}$, whenever there exists a black-box construction of $\mathcal{P}$ from $(\mathcal{Q},\mathcal{Z})$, then there must already also exist a black-box construction of $\mathcal{P}$ from $\mathcal{Z}$ alone. We also formalize various other notions of black-box uselessness, and consider in particular the setting of efficient black-box constructions when the number of queries to $\mathcal{Q}$ is below a threshold.

Impagliazzo and Rudich (STOC'89) initiated the study of black-box separations by separating key agreement from one-way functions. We prove a number of initial results in this direction, which indicate that one-way functions are perhaps also black-box useless for key agreement. In particular, we show that OWFs are black-box useless in any construction of key agreement in either of the following settings: (1) the key agreement has perfect correctness and one of the parties calls the OWF a constant number of times; (2) the key agreement consists of a single round of interaction (as in Merkle-type protocols). We conjecture that OWFs are indeed black-box useless for general key agreement protocols.

We also show that certain techniques for proving black-box separations can be lifted to the uselessness regime. In particular, we show that known lower bounds for assumptions behind black-box constructions of indistinguishability obfuscation (IO) can be extended to derive black-box uselessness of a variety of primitives for obtaining (approximately correct) IO. These results follow the so-called "compiling out" technique, which we prove to imply black-box uselessness.

Eventually, we study the complementary landscape of black-box uselessness, namely black-box helpfulness. Formally, we call primitive $\mathcal{Q}$ black-box helpful (BBH) for $\mathcal{P}$, if there exists an auxiliary primitive $\mathcal{Z}$ such that there exists a black-box construction of $\mathcal{P}$ from $(\mathcal{Q},\mathcal{Z})$, but there exists no black-box construction of $\mathcal{P}$ from $\mathcal{Z}$ alone.

We put forth the conjecture that one-way functions are black-box helpful for building collision-resistant hash functions. We define two natural relaxations of this conjecture, and prove that both of these conjectures are implied by a natural conjecture regarding random permutations equipped with a collision finder oracle, as defined by Simon (Eurocrypt'98). This conjecture may also be of interest in other contexts, such as hardness amplification.

###### Macarena Martínez-Rodríguez, Ignacio M. Delgado-Lozano, Billy Bob Brumley

ePrint Report###### Majid Salimi

ePrint Report###### Enric Florit, Benjamin Smith

ePrint Report###### Enric Florit, Benjamin Smith

ePrint Report###### Kwang Ho Kim, Jong Hyok Choe, Sihem Mesnager

ePrint ReportSubsequently, in \cite{Bluher2004,HK2008,HK2010,BTT2014,Bluher2016,KM2019,CMPZ2019,MS2019,KCM19}, the $\GF{Q}$-zeros of $P_a(X)$ have been studied. In \cite{Bluher2004}, it was shown that the possible values of the number of the zeros that $P_a(X)$ has in $\GF{Q}$ is $0$, $1$, $2$ or $p^{\gcd(n, k)}+1$. Some criteria for the number of the $\GF{Q}$-zeros of $P_a(x)$ were found in \cite{HK2008,HK2010,BTT2014,KM2019,MS2019}. However, while the ultimate goal is to explicit all the $\GF{Q}$-zeros, even in the case $p=2$, it was solved only under the condition $\gcd(n, k)=1$ \cite{KM2019}. In this article, we discuss this equation without any restriction on $p$ and $\gcd(n,k)$. In \cite{KCM19}, for the cases of one or two $\GF{Q}$-zeros, explicit expressions for these rational zeros in terms of $a$ were provided, but for the case of $p^{\gcd(n, k)}+1$ $\GF{Q}-$ zeros it was remained open to explicitly compute the zeros. This paper solves the remained problem, thus now the equation $X^{p^k+1}+X+a=0$ over $\GF{p^n}$ is completely solved for any prime $p$, any integers $n$ and $k$.

###### Seyit Camtepe, Jarek Duda, Arash Mahboubi, Pawel Morawiecki, Surya Nepal, Marcin Pawlowski, Josef Pieprzyk

ePrint ReportIn this work, we investigate natural properties of ANS that allow to incorporate authenticated encryption using as little cryptography as possible. We target low-level security communication such as transmission of data from IoT devices/sensors. In particular, we propose three solutions for joint compression and encryption (compcrypt). All of them use a pseudorandom bit generator (PRGB) based on lightweight stream ciphers. The first solution applies state jumps controlled by PRGB. The second one employs two ANS algorithms, where compression switches between the two. The switch is controlled by a PRGB bit. The third compcrypt modifies the encoding function of ANS depending on PRGB bits. Security and efficiency of the proposed compcrypt algorithms are evaluated.