## IACR News

Updates on the COVID-19 situation are on the
Announcement channel.

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

#### 10 February 2020

###### Hailong Yao, Caifen Wang*, Xingbing Fu, Chao Liu, Bin Wu, Fagen Li

ePrint Report
Recently, in IEEE Internet of Things Journal (DOI: 10.1109/JIOT.2019.2923373 ), Banerjee et al. proposed a lightweight anonymous authenticated key exchange scheme for IoT based on symmetric cryptography. In this paper, we show
that the proposal can not resist impersonation attacks due to vulnerable mutual authentication, and give improvements.

###### Erica Blum, Jonathan Katz, Julian Loss

ePrint Report
We study the problem of $\textit{state machine replication}$ (SMR) -- the underlying problem addressed by blockchain protocols -- in the presence of a malicious adversary who can corrupt some fraction of the parties running the protocol. Existing protocols for this task assume either a $\textit{synchronous network}$ (where all messages are delivered within some known time $\Delta$) or an $\textit{asynchronous network}$ (where messages can be delayed arbitrarily). Although protocols for the latter case give seemingly stronger guarantees, in fact they are incomparable since they (inherently) tolerate a lower fraction of corrupted parties.

We design an SMR protocol that is network-agnostic in the following sense: if it is run in a synchronous network, it tolerates $t_s$ corrupted parties; if the network happens to be asynchronous it is resilient to $t_a\leq t_s$ faults. Our protocol achieves optimal tradeoffs between $t_s$ and $t_a$.

We design an SMR protocol that is network-agnostic in the following sense: if it is run in a synchronous network, it tolerates $t_s$ corrupted parties; if the network happens to be asynchronous it is resilient to $t_a\leq t_s$ faults. Our protocol achieves optimal tradeoffs between $t_s$ and $t_a$.

###### Hila Dahari, Yehuda Lindell

ePrint Report
Zero-knowledge proof systems enable a prover to convince a verifier of the
validity of a statement without revealing anything beyond that fact. The role
of randomness in interactive proofs in general, and in zero-knowledge in
particular, is well known. In particular, zero-knowledge with a deterministic
verifier is impossible for non-trivial languages (outside of
$\mathcal{BPP}$). Likewise, it was shown by Goldreich and Oren (Journal of
Cryptology, 1994) that zero-knowledge with a deterministic prover is also
impossible for non-trivial languages. However, their proof holds only for
auxiliary-input zero knowledge and a malicious verifier.

In this paper, we initiate the study of the feasibility of zero-knowledge proof systems with a deterministic prover in settings not covered by the result of Goldreich and Oren. We prove the existence of deterministic-prover auxiliary-input honest-verifier zero-knowledge for any $\cal NP$ language, under standard assumptions. In addition, we show that any language with a hash proof system has a deterministic-prover honest-verifier statistical zero-knowledge proof, with an efficient prover. Finally, we show that in some cases, it is even possible to achieve deterministic-prover uniform zero-knowledge for a malicious verifier. Our contribution is primarily conceptual, and sheds light on the necessity of randomness in zero knowledge in settings where either the verifier is honest or there is no auxiliary input.

In this paper, we initiate the study of the feasibility of zero-knowledge proof systems with a deterministic prover in settings not covered by the result of Goldreich and Oren. We prove the existence of deterministic-prover auxiliary-input honest-verifier zero-knowledge for any $\cal NP$ language, under standard assumptions. In addition, we show that any language with a hash proof system has a deterministic-prover honest-verifier statistical zero-knowledge proof, with an efficient prover. Finally, we show that in some cases, it is even possible to achieve deterministic-prover uniform zero-knowledge for a malicious verifier. Our contribution is primarily conceptual, and sheds light on the necessity of randomness in zero knowledge in settings where either the verifier is honest or there is no auxiliary input.

###### Shaoquan Jiang, Guang Gong, Jingnan He, Khoa Nguyen, Huaxiong Wang

ePrint Report
Password-based authenticated key exchange (PAKE) allows two parties with a shared password to agree on a session key. In the last decade, the design of PAKE protocols from lattice assumptions has attracted lots of attention. However, existing solutions in the standard model do not have appealing efficiency. In this work, we first introduce a new PAKE framework. We then provide two realizations in the standard model, under the Learning With Errors (LWE) and Ring-LWE assumptions, respectively. Our protocols are much more efficient than previous proposals, thanks to three novel technical ingredients that may be of independent interests. The first ingredient consists of two approximate smooth projective hash (ASPH) functions from LWE, as well as two ASPHs from Ring-LWE. The latter are the first ring-based constructions in the literature, one of which only has a quasi-linear runtime while its function value contains $\Theta(n)$ field elements (where $n$ is the degree of the polynomial defining the ring). The second ingredient is a new key conciliation scheme that is approximately rate-optimal and that leads to a very efficient key derivation for PAKE protocols. The third one is a new authentication code that allows to verify a MAC with a noisy key.

###### Carmit Hazay, abhi shelat, Muthuramakrishnan Venkitasubramaniam

ePrint Report
The dual execution paradigm of Mohassel and Franklin (PKC'06) and Huang, Katz and Evans (IEEE '12) shows how
to achieve the notion of 1-bit leakage security at roughly twice the cost of semi-honest security for the special case of two-party secure computation. To date, there are no multi-party computation (MPC) protocols that offer such a strong trade-off between security and semi-honest performance.

Our main result is to address this shortcoming by designing 1-bit leakage protocols for the multi-party setting, albeit for a special class of functions. We say that function f(x,y) is efficiently verifiable by g if the running time of g is always smaller than f and g(x,y,z)=1 if and only if f(x,y)=z.

In the two-party setting, we first improve dual execution by observing that the ``second execution'' can be an evaluation of g instead of f, and that by definition, the evaluation of g is asymptotically more efficient.

Our main MPC result is to construct a 1-bit leakage protocol for such functions from any passive protocol for f that is secure up to additive errors and any active protocol for g. An important result by Genkin et al. (STOC '14) shows how the classic protocols by Goldreich et al. (STOC '87) and Ben-Or et al. (STOC '88) naturally support this property, which allows to instantiate our compiler with two-party and multi-party protocols.

A key technical result we prove is that the passive protocol for distributed garbling due to Beaver et al. (STOC '90) is in fact secure up to additive errors against malicious adversaries, thereby, yielding another powerful instantiation of our paradigm in the constant-round multi-party setting.

As another concrete example of instantiating our approach, we present a novel protocol for computing perfect matching that is secure in the 1-bit leakage model and whose communication complexity is less than the honest-but-curious implementations of textbook algorithms for perfect matching.

Our main result is to address this shortcoming by designing 1-bit leakage protocols for the multi-party setting, albeit for a special class of functions. We say that function f(x,y) is efficiently verifiable by g if the running time of g is always smaller than f and g(x,y,z)=1 if and only if f(x,y)=z.

In the two-party setting, we first improve dual execution by observing that the ``second execution'' can be an evaluation of g instead of f, and that by definition, the evaluation of g is asymptotically more efficient.

Our main MPC result is to construct a 1-bit leakage protocol for such functions from any passive protocol for f that is secure up to additive errors and any active protocol for g. An important result by Genkin et al. (STOC '14) shows how the classic protocols by Goldreich et al. (STOC '87) and Ben-Or et al. (STOC '88) naturally support this property, which allows to instantiate our compiler with two-party and multi-party protocols.

A key technical result we prove is that the passive protocol for distributed garbling due to Beaver et al. (STOC '90) is in fact secure up to additive errors against malicious adversaries, thereby, yielding another powerful instantiation of our paradigm in the constant-round multi-party setting.

As another concrete example of instantiating our approach, we present a novel protocol for computing perfect matching that is secure in the 1-bit leakage model and whose communication complexity is less than the honest-but-curious implementations of textbook algorithms for perfect matching.

###### Kostis Karantias, Aggelos Kiayias, Dionysis Zindros

ePrint Report
The abilities of smart contracts today are confined to reading from their own state. It is useful for a smart contract to be able to react to events and read the state of other smart contracts. In this paper, we devise a mechanism by which a derivative smart contract can read data, observe the state evolution, and react to events that take place in one or more underlying smart contracts of its choice. Our mechanism works even if the underlying smart contract is not designed to operate with the derivative smart contract. Like in traditional finance, derivatives derive their value (and more generally state) through potentially complex dependencies. We show how derivative smart contracts can be deployed in practice on the Ethereum blockchain without any forks or additional assumptions. We leverage any NIPoPoWs mechanism (such as FlyClient or superblocks) to obtain succinct proofs for arbitrary events, making proving them inexpensive for users. The latter construction is of particular interest, as it forms the first introspective SPV client: an SPV client for Ethereum in Ethereum. Last, we describe applications of smart contract derivatives which were not possible prior to our work, in particular the ability to create decentralized insurance smart contracts which insure an underlying on-chain security such as an ICO, as well as futures and options.

###### Christian Badertscher, Aggelos Kiayias, Markulf Kohlweiss, Hendrik Waldner

ePrint Report
In functional encryption (FE) a sender, Alice, encrypts plaintexts that a receiver, Bob, can obtain functional evaluations of, while Charlie is responsible for initializing the encryption keys and issuing the decryption keys. Standard notions of security for FE deal with a malicious Bob and how the confidentiality of Alice's messages can be maintained taking into account the leakage that occurs due to the functional keys that are revealed to the adversary via various forms of indistinguishability experiments that correspond to IND-CPA, IND-CCA and simulation-based security. In this work we provide a complete and systematic investigation of Consistency, a natural security property for FE, that deals with attacks that can be mounted by Alice, Charlie or a collusion of the two against Bob. We develop three main types of consistency notions according to which set of parties is corrupted and investigate their relation to the standard security properties of FE.

We then provide explicit constructions that achieve consistency either directly via a construction based on MDDH for specific function classes of inner products over a modulo group or generically for all the consistency types via compilers using standard cryptographic tools. Finally, we put forth a universally composable treatment of FE and we show that our consistency notions naturally complement FE security by proving how they imply (and are implied by) UC security depending on which set of parties is corrupted thereby yielding a complete characterization of consistency for FE.

We then provide explicit constructions that achieve consistency either directly via a construction based on MDDH for specific function classes of inner products over a modulo group or generically for all the consistency types via compilers using standard cryptographic tools. Finally, we put forth a universally composable treatment of FE and we show that our consistency notions naturally complement FE security by proving how they imply (and are implied by) UC security depending on which set of parties is corrupted thereby yielding a complete characterization of consistency for FE.

###### David Heath, Vladimir Kolesnikov

ePrint Report
Zero-knowledge (ZK) proofs (ZKP) have received wide attention, focusing on non-interactivity, short proof size, and fast verification time. We focus on the fastest total proof time, in particular for large Boolean circuits. Under this metric, Garbled Circuit (GC)-based ZKP (Jawurek et al., [JKO], CCS 2013) remained the state-of-the-art technique due to the low-constant linear scaling of computing the garbling.
We improve GC-ZKP for proof statements with conditional clauses. Our communication is proportional to the longest branch rather than to the entire proof statement. This is most useful when the number m of branches is large, resulting in up to factor $m\times$ improvement over JKO.
In our proof-of-concept illustrative application, prover P demonstrates knowledge of a bug in a codebase consisting of any number of snippets of actual C code. Our computation cost is linear in the size of the codebase and communication is constant in the number of snippets. That is, we require only enough communication for a single largest snippet!
Our conceptual contribution is stacked garbling for ZK, a privacy-free circuit garbling scheme that can be used with the JKO GC-ZKP protocol to construct more efficient ZKP. Given a Boolean circuit C and computational security parameter $\kappa$, the size of our garbling is $L \cdot \kappa$ bits, where $L$ is the length of the longest execution path in C. All prior garbling schemes produce garblings of size $|C| \cdot \kappa$. The computational cost of our scheme is not increased over prior state-of-the-art.
We implement our GC-ZKP and demonstrate significantly improved ($m\times$ over JKO) ZK performance for functions with branching factor $m$. Compared with recent ZKP (STARK, Libra, KKW, Ligero, Aurora, Bulletproofs), our scheme offers much better proof times for larger circuits ($35-1000\times$ or more, depending on circuit size and compared scheme). For our illustrative application, we consider four C code snippets, each of about 30-50 LOC; one snippet allows an invalid memory dereference. The entire proof takes 0.15 seconds and communication is 1.5 MB.

###### Abida Haque, Alessandra Scafuro

ePrint Report
A $t$-out-of-$N$ threshold ring signature allows $t$ parties to jointly and anonymously compute a signature on behalf on $N$ public keys, selected in an arbitrary manner among the set of all public keys registered in the system.

Existing definitions for $t$-out-of-$N$ threshold ring signatures guarantee security only when the public keys are honestly generated, and many even restrict the ability of the adversary to actively participate in the computation of the signatures. Such definitions do not capture the open settings envisioned for threshold ring signatures, where parties can independently add themselves to the system, and join other parties for the computation of the signature.

Furthermore, known constructions of threshold ring signatures are not provably secure in the post-quantum setting, either because they are based on non-post quantum secure problems (e.g. Discrete Log, RSA), or because they rely on transformations such as Fiat-Shamir, that are not always secure in the quantum random oracle model (QROM).

In this paper, we provide the first definition of $t$-out-of-$N$ threshold ring signatures against {\em active} adversaries who can participate in the system and arbitrarily deviate from the prescribed procedures. Second, we present a post-quantum secure realization based on {\em any} (post-quantum secure) trapdoor commitment, which we prove secure in the QROM. Our construction is black-box and it can be instantiated with any trapdoor commitment, thus allowing the use of a variety of hardness assumptions.

Existing definitions for $t$-out-of-$N$ threshold ring signatures guarantee security only when the public keys are honestly generated, and many even restrict the ability of the adversary to actively participate in the computation of the signatures. Such definitions do not capture the open settings envisioned for threshold ring signatures, where parties can independently add themselves to the system, and join other parties for the computation of the signature.

Furthermore, known constructions of threshold ring signatures are not provably secure in the post-quantum setting, either because they are based on non-post quantum secure problems (e.g. Discrete Log, RSA), or because they rely on transformations such as Fiat-Shamir, that are not always secure in the quantum random oracle model (QROM).

In this paper, we provide the first definition of $t$-out-of-$N$ threshold ring signatures against {\em active} adversaries who can participate in the system and arbitrarily deviate from the prescribed procedures. Second, we present a post-quantum secure realization based on {\em any} (post-quantum secure) trapdoor commitment, which we prove secure in the QROM. Our construction is black-box and it can be instantiated with any trapdoor commitment, thus allowing the use of a variety of hardness assumptions.

###### Vipul Goyal, Yifan Song

ePrint Report
We study the communication complexity of unconditionally secure MPC over point-to-point channels for corruption threshold t < n/2. We ask the question: "is it possible to achieve security-with-abort with the same concrete cost as the best-known semi-honest MPC protocol?" While a number of works have focused on improving the concrete efficiency in this setting, the answer to the above question has remained elusive until now.

We resolve the above question in the affirmative by providing a secure-with-abort MPC protocol with the same cost per gate as the best-known semi-honest protocol. Concretely, our protocol only needs 5.5 field elements per multiplication gate per party which matches (and even improves upon) the corresponding cost of the best known protocol in the semi-honest setting by Damgard and Nielsen. Previously best-known maliciously secure (with abort) protocols require 12 field elements. An additional feature of our protocol is its conceptual simplicity. Our result is achieved by relying on a novel technique of verifying a batch of multiplication tuples.

We resolve the above question in the affirmative by providing a secure-with-abort MPC protocol with the same cost per gate as the best-known semi-honest protocol. Concretely, our protocol only needs 5.5 field elements per multiplication gate per party which matches (and even improves upon) the corresponding cost of the best known protocol in the semi-honest setting by Damgard and Nielsen. Previously best-known maliciously secure (with abort) protocols require 12 field elements. An additional feature of our protocol is its conceptual simplicity. Our result is achieved by relying on a novel technique of verifying a batch of multiplication tuples.

###### Souradyuti Paul, Ananya Shrivastava

ePrint Report
In ACM CCS'17, Choudhuri et al. designed two fair public-ledger-based multi-party protocols (in the malicious model with dishonest majority) for computing an arbitrary function $f$. One of their protocols is based on a trusted hardware enclave $G$ (which can be implemented using Intel SGX-hardware) and a public ledger (which can be implemented using a blockchain platform, such as Ethereum). Subsequently, in NDSS'19, a stateless version of the protocol was published. This is the first time, (a certain definition of) fairness -- that guarantees either all parties learn the final output or nobody does -- is achieved without any monetary or computational penalties. However, these protocols are fair, if the underlying core MPC component guarantees both privacy and correctness. While privacy is easy to achieve (using a secret sharing scheme), correctness requires expensive operations (such as ZK proofs and commitment schemes). We improve on this work in three different directions: attack, design and performance.

Our first major contribution is building practical attacks that demonstrate: if correctness is not satisfied then the fairness property of the aforementioned protocols collapse. Next, we design two new protocols -- stateful and stateless -- based on public ledger and trusted hardware that are: resistant against the aforementioned attacks, and made several orders of magnitude more efficient (related to both time and memory) than the existing ones by eliminating ZK proofs and commitment schemes in the design.

Last but not the least, we implemented the core MPC part of our protocols using the SPDZ-2 framework to demonstrate the feasibility of its practical implementation.

Our first major contribution is building practical attacks that demonstrate: if correctness is not satisfied then the fairness property of the aforementioned protocols collapse. Next, we design two new protocols -- stateful and stateless -- based on public ledger and trusted hardware that are: resistant against the aforementioned attacks, and made several orders of magnitude more efficient (related to both time and memory) than the existing ones by eliminating ZK proofs and commitment schemes in the design.

Last but not the least, we implemented the core MPC part of our protocols using the SPDZ-2 framework to demonstrate the feasibility of its practical implementation.

###### Dario Fiore, Anca Nitulescu, David Pointcheval

ePrint Report
We consider the setting in which an untrusted server stores a collection of data and is asked to compute a function over it. In this scenario, we aim for solutions where the untrusted server does not learn information about the data and is prevented from cheating. This problem is addressed by verifiable and private delegation of computation, proposed by Gennaro, Gentry and Parno (CRYPTO’10), a notion that is close to both the active areas of homomorphic encryption and verifiable computation (VC). However, in spite of the efficiency advances in the respective areas, VC protocols that guarantee privacy of the inputs are still expensive. The only exception is a protocol by Fiore, Gennaro and Pastro (CCS’14) that supports arithmetic circuits of degree at most 2. In this paper we propose new efficient protocols for VC on encrypted data that improve over the state of the art solution of Fiore et al. in multiple aspects. First, we can support computations of degree higher than 2. Second, we achieve public delegatability and public verifiability whereas Fiore et al. need the same secret key to encode inputs and verify outputs. Third, we achieve a new property that guarantees that verifiers can be convinced about the correctness of the outputs without learning information on the inputs. The key tool to obtain our new protocols is a new SNARK that can efficiently handle computations over a quotient polynomial ring, such as the one used by Ring-LWE somewhat homomorphic encryption schemes. This SNARK in turn relies on a new commit-and-prove SNARK for proving evaluations on the same point of several committed polynomials. We propose a construction of this scheme under an extractability assumption over bilinear groups in the random oracle model.

###### Hamidreza Amini Khorasgani, Hemanta K. Maji, Mingyuan Wang

ePrint Report
There is a significant interest in securely computing functionalities with guaranteed output delivery, a.k.a, fair computation. For example, consider a 2-party $n$-round coin-tossing protocol in the information-theoretic setting. Even if one party aborts during the protocol execution, the other party has to receive her outcome. Towards this objective, every round, the sender of that round's message, preemptively prepares a defense coin, which is her output if the other party aborts prematurely. Cleve and Impagliazzo (1993), Beimel, Haitner, Makriyannis, and Eran Omri (2018), and Khorasgani, Maji, and Mukherjee (2019) show that a fail-stop adversary can alter the distribution of the outcome by $\Omega(1/\sqrt{n})$.

However, preparing the defense coin is computationally expensive. So, the parties would prefer to update their defense coin only sparingly or when indispensable. Furthermore, if parties delegate their coin-tossing task to an external server, it is even infeasible for the parties to stay abreast of the progress of the protocol and keep their defense coins in sync with the protocol evolution. Therefore, this paper considers lazy coin-tossing protocols, where parties update their defense coins only a total of $d$ times during the protocol execution. Is it possible that using only $d \ll n$ defense coin updates a fair coin-tossing protocol is robust to $\mathcal{O}({1/\sqrt{n}})$ change in their output distribution?

This paper proves that being robust to $\mathcal{O}({1/\sqrt{n}})$ change in the output distribution necessarily requires that the defense complexity $d=\Omega(n)$, thus ruling out the possibility mentioned above. More generally, our work proves that a fail-stop adversary can bias the outcome distribution of a coin-tossing protocol by $\Omega({1/\sqrt{d}})$, a qualitatively better attack than the previous state-of-the-art when $d=o({n})$. That is, the defense complexity of a coin-tossing protocol, not its round complexity, determines its security. We emphasize that the rounds where parties calculate their defense coins need not be a priori fixed; they can depend on the protocol's evolution itself. Finally, we translate this fail-stop adversarial attack into black-box separation results for lazy coin-tossing protocols.

The proof relies on an inductive argument using a carefully crafted potential function to precisely account for the quality of the best attack on coin-tossing protocols. Previous approaches fail when the protocol evolution reveals information about the defense coins of both the parties, which is inevitable in lazy coin-tossing protocols. Our analysis decouples the defense complexity of coin-tossing protocols from its round complexity to guarantee fail-stop attacks whose performance depends only on the defense complexity of the coin-tossing protocol; irrespective of their round complexity.

However, preparing the defense coin is computationally expensive. So, the parties would prefer to update their defense coin only sparingly or when indispensable. Furthermore, if parties delegate their coin-tossing task to an external server, it is even infeasible for the parties to stay abreast of the progress of the protocol and keep their defense coins in sync with the protocol evolution. Therefore, this paper considers lazy coin-tossing protocols, where parties update their defense coins only a total of $d$ times during the protocol execution. Is it possible that using only $d \ll n$ defense coin updates a fair coin-tossing protocol is robust to $\mathcal{O}({1/\sqrt{n}})$ change in their output distribution?

This paper proves that being robust to $\mathcal{O}({1/\sqrt{n}})$ change in the output distribution necessarily requires that the defense complexity $d=\Omega(n)$, thus ruling out the possibility mentioned above. More generally, our work proves that a fail-stop adversary can bias the outcome distribution of a coin-tossing protocol by $\Omega({1/\sqrt{d}})$, a qualitatively better attack than the previous state-of-the-art when $d=o({n})$. That is, the defense complexity of a coin-tossing protocol, not its round complexity, determines its security. We emphasize that the rounds where parties calculate their defense coins need not be a priori fixed; they can depend on the protocol's evolution itself. Finally, we translate this fail-stop adversarial attack into black-box separation results for lazy coin-tossing protocols.

The proof relies on an inductive argument using a carefully crafted potential function to precisely account for the quality of the best attack on coin-tossing protocols. Previous approaches fail when the protocol evolution reveals information about the defense coins of both the parties, which is inevitable in lazy coin-tossing protocols. Our analysis decouples the defense complexity of coin-tossing protocols from its round complexity to guarantee fail-stop attacks whose performance depends only on the defense complexity of the coin-tossing protocol; irrespective of their round complexity.

###### Elette Boyle, Ran Cohen, Aarushi Goel

ePrint Report
Byzantine agreement (BA), the task of $n$ parties to agree on one of their input bits in the face of malicious agents, is a powerful primitive that lies at the core of virtually every multi-party cryptographic protocol. Understanding the required communication complexity of BA as a function of $n$ is the subject of a rich line of research.

Interestingly, in protocols with the best overall communication complexity, the communication demands of the parties are highly unbalanced: the amortized cost is $\tilde O(1)$ bits per party, but some parties must send $\Omega(n)$ bits (e.g., Braud-Santoni et al., PODC'13). In best known balanced protocols, the overall communication is sub-optimal, with each party communicating $\tilde O(\sqrt{n})$ (e.g., King et al., ICDCN'11).

In this work, we ask whether asymmetry is inherent for optimizing total communication. In particular, is BA possible where each party sends and receives only $\tilde O(1)$ bits? Our contributions in this line are as follows:

1) We identify a cryptographic primitive---succinctly reconstructed distributed signatures (SRDS)---that suffices for constructing $\tilde O(1)$ balanced BA. We provide two constructions of SRDS: from one-way functions in a trustfully generated Public-Key Infrastructure (PKI) model, and from a strong form of succinct non-interactive arguments of knowledge in a weaker PKI model.

2) The SRDS-based BA follows a paradigm of boosting from "almost-everywhere" agreement (where $1-o(1)$ fraction of parties agree) to full agreement, and does so in a single round. Complementarily, we prove that PKI setup and cryptographic assumptions (alternatively, an even stronger, correlated-randomness setup assumption) are necessary for such protocols in which every party sends $o(n)$ messages.

3) We further explore connections between a natural approach toward attaining SRDS and average-case succinct non-interactive argument systems for a particular type of "Subset-$f$" problems (generalizing Subset-Sum and Subset-Product).

Collectively, our results provide an initial mapping for the feasibility landscape of $\tilde O(1)$ balanced BA, including new approaches forward, as well as limitations and barriers. Our approach yields the first two BA protocols with $\tilde O(1)$ balanced communication, offering a tradeoff between setup and cryptographic assumptions, and answering an open question presented by King and Saia (DISC'09).

Interestingly, in protocols with the best overall communication complexity, the communication demands of the parties are highly unbalanced: the amortized cost is $\tilde O(1)$ bits per party, but some parties must send $\Omega(n)$ bits (e.g., Braud-Santoni et al., PODC'13). In best known balanced protocols, the overall communication is sub-optimal, with each party communicating $\tilde O(\sqrt{n})$ (e.g., King et al., ICDCN'11).

In this work, we ask whether asymmetry is inherent for optimizing total communication. In particular, is BA possible where each party sends and receives only $\tilde O(1)$ bits? Our contributions in this line are as follows:

1) We identify a cryptographic primitive---succinctly reconstructed distributed signatures (SRDS)---that suffices for constructing $\tilde O(1)$ balanced BA. We provide two constructions of SRDS: from one-way functions in a trustfully generated Public-Key Infrastructure (PKI) model, and from a strong form of succinct non-interactive arguments of knowledge in a weaker PKI model.

2) The SRDS-based BA follows a paradigm of boosting from "almost-everywhere" agreement (where $1-o(1)$ fraction of parties agree) to full agreement, and does so in a single round. Complementarily, we prove that PKI setup and cryptographic assumptions (alternatively, an even stronger, correlated-randomness setup assumption) are necessary for such protocols in which every party sends $o(n)$ messages.

3) We further explore connections between a natural approach toward attaining SRDS and average-case succinct non-interactive argument systems for a particular type of "Subset-$f$" problems (generalizing Subset-Sum and Subset-Product).

Collectively, our results provide an initial mapping for the feasibility landscape of $\tilde O(1)$ balanced BA, including new approaches forward, as well as limitations and barriers. Our approach yields the first two BA protocols with $\tilde O(1)$ balanced communication, offering a tradeoff between setup and cryptographic assumptions, and answering an open question presented by King and Saia (DISC'09).

###### Juliane Krämer, Patrick Struck

ePrint Report
The security proofs of post-quantum cryptographic schemes often consider only classical adversaries. Therefore, whether such schemes are really post-quantum secure remains unknown until the proofs take quantum adversaries into account. Switching to a quantum adversary might require to adapt the security notion. In particular, post-quantum security proofs for schemes which use random oracles have to be in the quantum random oracle model (QROM), while classical security proofs are in the random oracle model (ROM). We remedy this state of affairs by introducing a framework to obtain the post-quantum security of public key encryption schemes which use random oracles. We define a class of encryption schemes, called oracle-simple, and identify game hops which are used to prove such schemes secure in the ROM. For these game hops, we state both simple and sufficient conditions to validate that a proof also holds in the QROM. The strength of our framework lies in its simplicity, its generality, and its applicability. We demonstrate this by applying it to the code-based encryption scheme ROLLO (Round 2 NIST candidate) and the lattice-based encryption scheme LARA (FC 2019). This proves that both schemes are post-quantum secure, which had not been shown before.

###### University of Tartu, Estonia

Job Posting
The Cryptography, Coding and Information Transmission Group at the University of Tartu, Estonia, is looking for a doctorate student for a project on coding for flash memories. The ideal candidate will have strength in one or more of the following areas:

• Any area related to coding theory

• Combinatorics

• Algebra

• Probability theory

• Algorithms and programming.

The income is at least 1060 euro per month (net) plus social benefits. Some travel money will also be available. Cost of living in Estonia is relatively low, see e.g. https://www.ut.ee/en/welcome/international-students and http://www.expatistan.com/cost-of-living . A successful candidate should:

• Hold a Master’s degree or equivalent before the start of studies (Fall 2020)

• Have a strong background in mathematics, computer science or a related field.

To apply, please submit the following documents (by email):

• Application letter

• Research statement (preliminary plan)

• Curriculum vitae

• Publication list or example publication / thesis (optional)

• Copies of documents about academic degrees

• Two letters of reference (make sure they reach us by the application deadline).

Deadline for applications: 24th February 2020. Do not hesitate to contact us in case of questions. Contact: Ago-Erik Riet, e-mail agoerik at ut.ee, see https://www.etis.ee/Portal/Persons/Display/fa2b849b-a7cb-4463-aefd-01603d27ebc6?tabId=CV_ENG , https://www.ut.ee/en/kontakt/matemaatika-statistika-instituut and http://cit.cs.ut.ee/ . For a formal advertisement please also see: https://www.ut.ee/en/phd-mathematics .

• Any area related to coding theory

• Combinatorics

• Algebra

• Probability theory

• Algorithms and programming.

The income is at least 1060 euro per month (net) plus social benefits. Some travel money will also be available. Cost of living in Estonia is relatively low, see e.g. https://www.ut.ee/en/welcome/international-students and http://www.expatistan.com/cost-of-living . A successful candidate should:

• Hold a Master’s degree or equivalent before the start of studies (Fall 2020)

• Have a strong background in mathematics, computer science or a related field.

To apply, please submit the following documents (by email):

• Application letter

• Research statement (preliminary plan)

• Curriculum vitae

• Publication list or example publication / thesis (optional)

• Copies of documents about academic degrees

• Two letters of reference (make sure they reach us by the application deadline).

Deadline for applications: 24th February 2020. Do not hesitate to contact us in case of questions. Contact: Ago-Erik Riet, e-mail agoerik at ut.ee, see https://www.etis.ee/Portal/Persons/Display/fa2b849b-a7cb-4463-aefd-01603d27ebc6?tabId=CV_ENG , https://www.ut.ee/en/kontakt/matemaatika-statistika-instituut and http://cit.cs.ut.ee/ . For a formal advertisement please also see: https://www.ut.ee/en/phd-mathematics .

**Closing date for applications:**

**Contact:** Ago-Erik Riet

#### 07 February 2020

###### Cispa, Helmholtz center for Cybersecurity

Job Posting
In the context of the Almacrypt ERC, CISPA has several postdoctoral positions related to the study of cryptographic hard problems.

The proposed topics are discrete logarithms and factoring, lattice reduction, multivariate equation systems, elliptic curves and combinatorial problems of cryptographic relevance.

Strong applicants in symmetric cryptography might also be considered.

Candidates should have a PhD in Cryptology, Number theory or theoretical Computer Science.

The application should contain a research program for the desired length of the position (up to three years).

All applications should be through the provided web-interface.

The proposed topics are discrete logarithms and factoring, lattice reduction, multivariate equation systems, elliptic curves and combinatorial problems of cryptographic relevance.

Strong applicants in symmetric cryptography might also be considered.

Candidates should have a PhD in Cryptology, Number theory or theoretical Computer Science.

The application should contain a research program for the desired length of the position (up to three years).

All applications should be through the provided web-interface.

**Closing date for applications:**

**Contact:** Antoine Joux

**More information:** https://jobs.cispa.saarland/jobs/detail/post-doc-in-mathematical-and-or-algorithmic-cryptography-38

###### Cispa, Helmholtz center for Cybersecurity

Job Posting
In the context of the Almacrypt ERC, CISPA has several phD positions related to the study of cryptographic hard problems. The proposed topics are discrete logarithms and factoring, lattice reduction, multivariate equation systems, elliptic curves and combinarial problems of cryptographic relevance.

Candidates should have a strong background in Mathematics or theoretical Computer Science. Knowledge of cryptology would be a plus.

The application should specify (and justify) the specific domain of interest of the candidate.

All applications should be through the provided web-interface.

Candidates should have a strong background in Mathematics or theoretical Computer Science. Knowledge of cryptology would be a plus.

The application should specify (and justify) the specific domain of interest of the candidate.

All applications should be through the provided web-interface.

**Closing date for applications:**

**Contact:** Antoine Joux

**More information:** https://jobs.cispa.saarland/jobs/detail/phd-in-mathematical-and-or-algorithmic-cryptography-39

#### 06 February 2020

###### Ward Beullens, Cyprien Delpech de Saint Guilhem

ePrint Report
We introduce an efficient post-quantum signature scheme that relies on the one-wayness of the Legendre PRF. This "LEGendRe One-wAyness SignaTure" (LegRoast) builds upon the MPC-in-the-head technique to construct an efficient zero-knowledge proof, which is then turned into a signature scheme with the Fiat-Shamir transform. Unlike many other Fiat-Shamir signatures, the security of LegRoast can be proven without using the forking lemma, and this leads to a tight (classical) ROM proof. We also introduce a generalization that relies on the one-wayness of higher-power residue characters; the "POwer Residue ChaRacter One-wAyness SignaTure" (PorcRoast).

LegRoast outperforms existing MPC-in-the-head-based signatures (most notably Picnic/Picnic2) in terms of signature size and speed. Moreover, PorcRoast outperforms LegRoast by a factor of 2 in both signature size and signing time. For example, one of our parameter sets targeting NIST security level I results in a signature size of 7.2 KB and a signing time of 2.8ms. This makes PorcRoast the most efficient signature scheme based on symmetric primitives to date.

LegRoast outperforms existing MPC-in-the-head-based signatures (most notably Picnic/Picnic2) in terms of signature size and speed. Moreover, PorcRoast outperforms LegRoast by a factor of 2 in both signature size and signing time. For example, one of our parameter sets targeting NIST security level I results in a signature size of 7.2 KB and a signing time of 2.8ms. This makes PorcRoast the most efficient signature scheme based on symmetric primitives to date.

###### Véronique Cortier, Joseph Lallemand, Bogdan Warinschi

ePrint Report
We propose a framework for the analysis of electronic voting schemes in the presence of malicious bulletin boards. We identify a spectrum of notions where the adversary is allowed to tamper with the bulletin board in ways that reflect practical deployment and usage considerations. To clarify the security guarantees provided by the different notions we establish a relation with simulation-based security with respect to a family of ideal functionalities. The ideal functionalities make clear the set of authorised attacker capabilities which makes it easier to understand and compare the associated levels of security. We then leverage this relation to show that each distinct level of ballot privacy entails some distinct form of individual verifiability. As an application, we study three protocols of the literature (Helios, Belenios, and Civitas) and identify the different levels of privacy they offer.