## 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:

#### 15 January 2020

###### Yupu Hu, Siyue Dong, Xingting Dong
ePrint Report
Aigis-Enc is an encryption algorithm based on asymmetrical LWE. In this algorithm, the compression process is utilized during both key generation and encryption (which is equivalent to add some LWR noise). Then encapsulation is realized by FO transformation. It is well known that FO transformation is not considered for discussing CPA security. On the other hand, since the security reduction of LWR is hard to proceed, it is not considered for discussing the CPA security of Aigis-Enc. But compression must be put into consideration when we discuss decryption failure probability. In other words, when we discuss the CPA security of Aigis-Enc, the compression and FO transformation are ignored. But when decryption failure probability is discussed, compression should be taken into consideration while FO transformation remains ignored.

According to the assumptions above, Aigis-Enc designers claim that the CPA security of Aigis-Enc is approximately equal to that of the symmetrical LWE scheme in the same scale, and the decryption failure probability of Aigis-Enc is far below that of the symmetrical LWE scheme in the same scale.

In this paper, we make a thorough comparison between Aigis-Enc (with the recommended parameters) and the symmetrical LWE encryption scheme in the same scale. Our conclusion is as followed:

(1) The comparison on CPA security. The former’s is 160.898, and the latter’s is 161.836.

(2) The comparison on computation complexity. In key generation phase, the ratio of the former and the latter on sampling amount of distribution $\left[ {\begin{array}{*{20}{c}} 0&1\\ {\frac{1}{2}}&{\frac{1}{2}} \end{array}} \right]$ is 5:4; In encryption phase, that ratio is 19:14. The other computations remain the same.

(3) The comparison on decryption failure probability. The former’s is $2^{-128.699}$, the latter's is $2^{-67.0582}$. The comparison seems to be dramatic. But in fact, we can slightly increase some traffic to keep failure probability unchanged. In other words, by compressing less to keep decryption failure probability unchanged. In specific: we change the parameters $\left( {{d_1},{d_2},{d_3}} \right)$ from $\left( {9,9,4} \right)$ to $\left( {10,10,4} \right)$, which means a large part of the public key remains the same, the small part of the public key changes from 9 bits per entry into 10bits. A large part of the ciphertext changes from 9 bits per entry into 10 bits, the small part of the ciphertext remains the same. As thus, the communication traffic increases less than $\frac{1}{9}$, while the decryption failure probability is lower than $2^{-128.699}$.

We generalize those attacks presented by designers of Aigis-Enc, including primal attacks and dual attacks. More detailedly, our attacks are more extensive, simpler, and clearer. With them, we obtain the optimal attacks and “the optimal-optimal attack” on Aigis-Enc and the symmetrical LWE scheme in the same scale.

#### 13 January 2020

###### Rakyong Choi, Dongyeon Hong, Kwangjo Kim
ePrint Report
In this paper, we propose a novel lattice-based group key exchange protocol with dynamic membership. Our protocol is constructed by generalizing Dutta-Barua protocol to RLWE setting, inspired by Apon et al.’s recent paper in PQCrypto 2019. We describe our (static) group key exchange protocol from Apon et al.’s paper by modifying its third round and computation step. Then, we present both authenticated and dynamic group key exchange protocol with Join and Leave algorithms. The number of rounds for authenticated group key exchange remains the same as unauthenticated one. Our protocol also supports the scalable property so that the number of rounds does not change depending on the number of group participants. By assuming the hardness of RLWE assumption and unforgeability of digital signatures, we give a full security proof for (un-)authenticated (dynamic) group key exchange protocols.
###### Tianjun Ma, Haixia Xu, Peili Li
ePrint Report
Many studies focus on the blockchain privacy protection. Unfortunately, the privacy protection brings regulatory issues (e.g., countering money-laundering). Tracing users' identities is a critical step in addressing blockchain regulatory issues. In this paper, we propose SkyEye, a traceable scheme for blockchain. SkyEye can be applied to the blockchain applications that satisfy the following conditions: (I) The users have public and private information, where the public information is generated by the private information; (II) The users' public information is disclosed in the blockchain data. SkyEye enables the regulator to trace users' identities. The design of SkyEye leverages some cryptographic primitives, including chameleon hash and zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARK). Moreover, we demonstrate the security of SkyEye under specific cryptographic assumptions. Finally, we implement two prototypes of SkyEye, and evaluate the running time and related data storage requirements by performing the aforementioned prototypes.
###### Mohamed Seifelnasr, Hisham S. Galal, Amr M. Youssef
ePrint Report
McCorry et al. (Financial Cryptography 2017) presented the first implementation of a decentralized self-tallying voting protocol on Ethereum. However, their implementation did not scale beyond 40 voters since all the computations were performed on the smart contract. In this paper, we tackle this problem by delegating the bulk computations to an off-chain untrusted administrator in a verifiable manner. Specifically, the administrator tallies the votes off-chain and publishes a Merkle tree that encodes the tallying computation trace. Then, the administrator submits the Merkle tree root and the tally result to the smart contract. Subsequently, the smart contract transits to an intermediate phase where at least a single honest voter can contend the administrator's claimed result if it was not computed correctly. Then, in the worst case, the smart contract verifies the dispute at the cost of an elliptic curve point addition and scalar multiplication, and two Merkle proofs of membership which are logarithmic in the number of voters. This allows our protocol to achieve higher scalability without sacrificing the public verifiability or voters' privacy. To assess our protocol, we implemented an open-source prototype on Ethereum and carried out multiple experiments for different numbers of voters. The results of our implementation confirm the scalability and efficiency of our proposed solution which does not exceed the current block gas limit for any practical number of voters.
ePrint Report
In this paper, we propose a method for implementing binary matrices with low-cost XOR. First, using a random-iterative method, we obtain a list S from a binary matrix A. Then, based on the list S, we construct a binary matrix B. Next, we find a relation between the implementations of A and B. In other words, using the implementation of the matrix B, we get a low-cost implementation for the matrix A. Also, we show that the implementation of an MDS matrix M is associated with the form of the binary matrix used to construct the binary form of M. In addition, we propose a heuristics algorithm to implement MDS matrices. The best result of this paper is the implementation of a 8 × 8 involutory MDS matrix over 8-bit words with 408 XOR gates. The Paar algorithm is used as an SLP application to obtain implementations of this paper.
###### Kuan Cheng, Xin Li, Yu Zheng
ePrint Report
We initiate a study of locally decodable codes with randomized encoding. Standard locally decodable codes are error correcting codes with a deterministic encoding function and a randomized decoding function, such that any desired message bit can be recovered with good probability by querying only a small number of positions in the corrupted codeword. This allows one to recover any message bit very efficiently in sub-linear or even logarithmic time. Besides this straightforward application, locally decodable codes have also found many other applications such as private information retrieval, secure multiparty computation, and average-case complexity.

However, despite extensive research, the tradeoff between the rate of the code and the number of queries is somewhat disappointing. For example, the best known constructions still need super-polynomially long codeword length even with a logarithmic number of queries, and need a polynomial number of queries to achieve a constant rate. In this paper, we show that by using a randomized encoding, in several models we can achieve significantly better rate-query tradeoff. In addition, our codes work for both the standard Hamming errors, and the more general and harder edit errors.
###### Michael Kounavis, Sergej Deutsch, Santosh Ghosh, David Durham
ePrint Report
We present the design of a novel low latency, bit length parameterizable cipher, called the K-Cipher''. K-Cipher is particularly useful to applications that need to support ultra low latency encryption at arbitrary ciphertext lengths. We can think of a range of networking, gaming and computing applications that may require encrypting data at unusual block lengths for many different reasons, such as to make space for other unencrypted state values. Furthermore, in modern applications, encryption is typically required to complete inside stringent time frames in order not to affect performance. K-Cipher has been designed to meet these requirements. In the paper we present the K-Cipher design and discuss its rationale.
###### Seung Geol Choi, Dana Dachman-Soled, Mukul Kulkarni, Arkady Yerukhimovich
ePrint Report
We consider a scenario where multiple organizations holding large amounts of sensitive data from their users wish to compute aggregate statistics on this data while protecting the privacy of individual users. To support large-scale analytics we investigate how this privacy can be provided for the case of sketching algorithms running in time sub-linear of the input size.

We begin with the well-known LogLog sketch for computing the number of unique elements in a data stream. We show that this algorithm already achieves differential privacy (even without adding any noise) when computed using a private hash function by a trusted curator. Next, we show how to eliminate this requirement of a private hash function by injecting a small amount of noise, allowing us to instantiate an efficient LogLog protocol for the multi-party setting. To demonstrate the practicality of this approach, we run extensive experimentation on multiple datasets, including the publicly available IP address data set from University of Michigan’s scans of internet IPv4 space, to determine the tradeoffs among efficiency, privacy and accuracy of our implementation for varying numbers of parties and input sizes.

Finally, we generalize our approach for the LogLog sketch and obtain a general framework for constructing multi-party differentially private protocols for several other sketching algorithms.
###### Denis Firsov, Ahto Buldas, Ahto Truu, Risto Laanoja
ePrint Report
The majority of real-world applications of digital signatures use timestamping to ensure non-repudiation in face of possible key revocations. This observation led Buldas, Laanoja, and Truu to a server-assisted digital signature scheme built around cryptographic timestamping.

In this paper, we report on the machine-checked proofs of existential unforgeability under the chosen-message attack (EUF-CMA) of some variations of BLT digital signature scheme. The proofs are developed and verified using the EasyCrypt framework, which provides interactive theorem proving supported by the state-of-the-art SMT solvers.

#### 10 January 2020

###### Daejeon, South Korea, 6 December - 10 December 2020
Asiacrypt
Event date: 6 December to 10 December 2020

#### 09 January 2020

###### Alexander Maximov
ePrint Report
In this paper we consider several methods for an efficient extraction of roots of a polynomial over large finite fields. The problem of computing such roots is often the performance bottleneck for some multivariate quantum-immune cryptosystems, such as HFEv-based Quartz, Gui, etc. We also discuss a number of techniques for fast computation of traces as part of the factorization process. These optimization methods could significantly improve the performance of cryptosystems where roots factorization is a part thereof.
###### Wen Wang, Marc Stöttinger
ePrint Report
The rapid development of IT in the automotive industry has driven increasing requirements on incorporating security functionalities in the in-vehicle architecture, which is usually realized by adding a Hardware Secure Module (HSM) in the Electronic Central Unit (ECU). Therefore, secure communications can be enforced by carrying out secret cryptographic computations within the HSM by use of the embedded hardware accelerators. However, there is no common standard for designing the architecture for an HSM. A future design of a common automotive HSM is desired by the automotive industry which not only fits to the increasing performance demand, but also further defends against future attacks by attackers exploiting large-scale quantum computers. The arrival of future quantum computers motivates the investigation into post-quantum cryptography (PQC), which will retain the security of an HSM in the future. We analyzed the candidates in NIST’s PQC standardization process, and proposed new sets of hardware accelerators for the future generation of the automotive HSMs. Our evaluation results show that building a post-quantum secure automotive HSM is feasible and can meet the hard requirements imposed by a modern vehicle ECU.
###### Dan Boneh, Saba Eskandarian, Lucjan Hanzlik, Nicola Greco
ePrint Report
In a Single Secret Leader Election (SSLE), a group of participants aim to randomly choose exactly one leader from the group with the restriction that the identity of the leader will be known to the chosen leader and nobody else. At a later time, the elected leader should be able to publicly reveal her identity and prove that she has won the election. The election process itself should work properly even if many registered users are passive and do not send any messages. Among the many applications of SSLEs, their potential for enabling more efficient proof-of-stake based cryptocurrencies have recently received increased attention.

This paper formally defines SSLE schemes and presents three constructions that provide varying security and performance properties. First, as an existence argument, we show how to realize an ideal SSLE using indistinguishability obfuscation. Next, we show how to build SSLE from low-depth threshold fully homomorphic encryption (TFHE) via a construction which can be instantiated with a circuit of multiplicative depth as low as 10, for realistically-sized secret leader elections. Finally, we show a practical scheme relying on DDH that achieves a slightly relaxed notion of security but which boasts extremely lightweight computational requirements.
###### Ethan Heilman, Sebastien Lipmann, Sharon Goldberg
ePrint Report
The Arwen Trading Protocols are layer-two blockchain protocols for traders to securely trade cryptocurrencies at a centralized exchange, without ceding custody of their coins to the exchange. Before trading begins, traders deposit their coins in an on-blockchain escrow where the agent of escrow is the blockchain itself. Each trade is backed by the coins locked in escrow. Each trade is fast, because it happens off-blockchain, and secure, because atomic swaps prevent even a hacked exchange from taking custody of a trader’s coins. Arwen is designed to work even with the "lowest common denominator" of blockchains—namely Bitcoin-derived coins without SegWit support. As a result, Arwen supports essentially all "Bitcoin-derived" coins e.g., BTC, LTC, BCH, ZEC, as well as Ethereum. Our protocols support Limit and RFQ order types, we implemented our RFQ protocol and are available for use at arwen.io.
###### Riccardo Longo, Alessio Meneghetti, Massimiliano Sala
ePrint Report
Key custody is a sensitive aspect of cryptocurrencies. The employment of a custodian service together with threshold-multi-party signatures helps to manage secret keys more safely and effectively, e.g. allowing the recovery of crypto-assets when users lose their own keys. Advancing from a protocol by Gennaro et al. we propose a protocol with two main properties. First it allows the recovery party to remain offline during the enrollment of any user, solving a real-life problem of maintaining online only one trusted third party. Second our multi-party signature is compatible with a deterministic derivation of public and private keys.
###### Zagreb, Croatia, 24 June - 26 June 2020
Event Calendar
Event date: 24 June to 26 June 2020
###### Daejeon, South Korea, 6 December - 10 December 2020
Asiacrypt
Event date: 6 December to 10 December 2020
###### Daejeon, South Korea, 6 December - 10 December 2020
Asiacrypt
Event date: 6 December to 10 December 2020

#### 08 January 2020

###### Stealth Software Technologies, Inc. Los Angeles CA and Boulder CO
Job Posting
Stealth Software Technologies is looking for recent graduates in theoretical and applied cryptography, coding theory, combinatorics, and programming languages. We perform cutting-edge research and software development in multiple areas of cryptography, including Zero-Knowledge, Multi-Party Computation, Private Set Intersection, Searchable Encryption, Distributed Consensus and other cryptographic algorithms and tool chains. Our team consists of several IACR Fellows and numerous research faculty members across the U.S. and the world, and we are deeply connected with the crypto community. As such, working for Stealth will provide you with the opportunity to continue working on challenging academic problems at the forefront of crypto and security research, as well as helping design novel software prototypes that leverage the latest cryptographic techniques to optimize security and performance.

Required Qualifications:

• Ph.D. in computer science, mathematics or a related field
• Active track record of relevant publications
• Proficiency in programming, especially C, C++ or Java
Work Authorization:
United States, US Citizen strongly preferred

Benefits:
• Salary commensurate with experience
• Flexible workspace (offices in West L.A. and Boulder, remote commuting available)
• Paid Vacation and Holidays
• Retirement plan (401K)
• Health, Dental, and Vision insurance reimbursement coverage
• Equity in the form of Stock Options
• Opportunity for growth and advancement
• Collaboration with world-class cryptographers with publication opportunities

To Apply:

Send a cover letter, Curriculum Vitae with at least two references to careers@stealthsoftwareinc.com

As part of a successful hiring process, the applicant agrees to submit to a background check.

Closing date for applications:

Contact:
Job Search Committee
careers@stealthsoftwareinc.com

###### IT University of Copenhagen (ITU)
Job Posting

The Center for Information Security and Trust and the IT University of Copenhagen (ITU) is hiring one Postdoc and one PhD Student to work on cryptographic protocols for Multiparty Computation (MPC) and Blockchain Consensus/Applications. Both positions are fully funded by DFF (Danish funding agency) for a period of 3 years and start around April 2020. Successful candidates will be hired at ITU with standard wages according to union agreements in Denmark and access to public health/education.

Both the successful Postdoc and PhD student will work on projects related to theoretical aspects of MPC and blockchain protocols, as well as the interplay between these two fields. One line of work will focus on obtaining new theoretical insights and better constructions of MPC protocols with public verifiability, cheater identification and similar properties. Another line of work will focus on establishing foundations of protocols forauditable privacy preserving blockchain applications as well as employing MPC techniques to build such protocols.

The successful applicant to the PhD Student position should be motivated and enthusiastic about theoretical research in cryptography. The application should have a strong background in computer science or mathematics (with a focus on number theory, algebra and probability theory). Previous research experience in security and cryptography (specially in cryptographic protocols) is not necessary but most welcome.

The successful applicant to the Postdoc position should hold (or be about to complete) a PhD degree in Computer Science (and related areas) with a focus on cryptographic protocols. Applicants should have an excellent academic track record with publications in relevant venues (e.g. IACR conferences). Previous experience in all aspects of Multiparty Computation protocols and theoretical aspects of blockchain protocols (both consensus and applications) is an advantage.

Closing date for applications:

Contact: Associate Professor Bernardo David