International Association
for Cryptologic Research

Devising efficient and secure signature schemes based on coding theory is still considered a challenge by the cryptographic community. In this paper, we construct a signature scheme by exploring a new approach to the area. To do this, we design a zero-knowledge identification scheme, which we then render static via standard means (e.g. Fiat-Shamir). We show that practical instances of our protocol have the potential to outperform the state of the art on code-based signatures, achieving small data sizes with a low computational complexity.

Many alt-coins developed in recent years make strong privacy guarantees, claiming to be virtually untraceable. This paper explores the extent to which these claims are true after the first appraisals were made about these coins. In particular, we will investigate Monero (XMR) and Zcash (ZEC), competitors in the private cryptocurrency space. We will test how traceable these currencies are after the most recent security updates, and how they hold up against their claims. We run some traceability experiments based on previously published papers for each coin. Results show that, introducing strict security and anonymity requirements into the cryptocurrency ecosystem makes the coin effectively untraceable, as shown by Monero. On the other hand, Zcash still hesitates to introduce changes that alter user behavior. Despite its strong cryptographic features, transactions are overall more traceable.

Performing ML computation on private data while maintaining data privacy aka Privacy-preserving Machine Learning (PPML) is an emergent field of research. Recently, PPML has seen a visible shift towards the adoption of Secure Outsourced Computation (SOC) paradigm, due to the heavy computation that it entails. In the SOC paradigm, computation is outsourced to a set of powerful and specially equipped servers that provide service on a pay-per-use basis. In this work, we propose SWIFT, a robust PPML framework for a range of ML algorithms in SOC setting, that guarantees output delivery to the users irrespective of any adversarial behaviour. Robustness, a highly desirable feature, evokes user participation without the fear of denial of service.

At the heart of our framework lies a highly-efficient, maliciously-secure, three-party computation (3PC) over rings that provides guaranteed output delivery (GOD) in the honest-majority setting. To the best of our knowledge, SWIFT is the first robust and efficient PPML framework in the 3PC setting. SWIFT is as fast as the best-known 3PC framework BLAZE (Patra et al. NDSS'20) which only achieves fairness. We extend our 3PC framework for four parties (4PC). In this regime, SWIFT is as fast as the best known fair 4PC framework Trident (Chaudhari et al. NDSS'20) and twice faster than the best-known robust 4PC framework FLASH (Byali et al. PETS'20).

We demonstrate the practical relevance of our framework by benchmarking two important applications-- i) ML algorithms: Logistic Regression and Neural Network, and ii) Biometric matching, both over a 64-bit ring in WAN setting. Our readings reflect our claims as above.

Since Keccak was selected as the SHA-3 standard, more and more permutation-based primitives have been proposed. Different from block ciphers, there is no round key in the underlying permutation for permutation-based primitives. Therefore, there is a higher risk for a differential characteristic of the underlying permutation to become incompatible when considering the dependency of difference transitions over different rounds. However, in most of the MILP or SAT based models to search for differential characteristics, only the difference transitions are involved and are treated as independent in different rounds, which may cause that an invalid one is found for the underlying permutation. To overcome this obstacle, we are motivated to design a model which automatically avoids the inconsistency in the search for differential characteristics. Our technique is to involve both the difference transitions and value transitions in the constructed model. Such an idea is inspired by the algorithm to find SHA-2 characteristics as proposed by Mendel et al. in ASIACRYPT 2011, where the differential characteristic and the conforming message pair are simultaneously searched. As a first attempt, our new technique will be applied to the Gimli permutation, which was proposed in CHES 2017. As a result, we reveal that some existing differential characteristics of reduced Gimli are indeed incompatible, one of which is found in the Gimli document. In addition, since only the permutation is analyzed in the Gimli document, we are lead to carry out a comprehensive study, covering the proposed hash scheme and the authenticated encryption (AE) scheme specified for Gimli, which has become a second round candidate of the NIST lightweight cryptography standardization process. For the hash scheme, a semi-free-start (SFS) collision attack can reach up to 8 rounds starting from an intermediate round. For the AE scheme, a state recovery attack is demonstrated to achieve up to 9 rounds. It should be emphasized that our analysis does not threaten the security of Gimli.

Byzantine Broadcast (BB) is a central question in distributed systems, and an important challenge is to understand its round complexity. Under the honest majority setting, it is long known that there exist randomized protocols that can achieve BB in expected constant rounds, regardless of the number of nodes $n$. However, whether we can match the expected constant round complexity in the corrupt majority setting --- or more precisely, when $f \geq n/2 + \omega(1)$ --- remains unknown, where $f$ denotes the number of corrupt nodes.

In this paper, we are the first to resolve this long-standing question. We show how to achieve BB in expected $O((n/(n-f))^2)$ rounds. In particular, even when 99\% of the nodes are corrupt we can achieve expected constant rounds.Our results hold under both a static adversary and a weakly adaptive adversary who cannot perform ``after-the-fact removal'' of messages already sent by a node before it becomes corrupt.

This paper proposes new symmetric cryptoalgorithms of Residue Number System and its Modified Perfect Form. According to the first method, ciphertext is regarded as a set of residues to the corresponding sets of modules (keys) and decryption or decimal number recovery from its residues takes place according to the Chinese remainder theorem. To simplify the calculations, it is proposed to use a Modified Perfect Form of Residue Number System, which leads to a decrease in the number of arithmetic operations (in particular, finding the inverse and multiplying by it) during the decryption process. Another method of symmetric encryption based on the Chinese remainder theorem can be applied when fast decryption is required. In this algorithm, the plaintext block is divided into sub-blocks that are smaller than the corresponding module and serve as remainders on dividing some number, which is a ciphertext, by these modules. Plaintext recovery is based on finding the ciphertext remainders to the corresponding modules. Examples of cryptoalgorithms implementation and their encryption schemes are given. Cryptosecurity of the proposed methods is estimated on the basis of the Prime number theorem and the Euler function. It is investigated which bitness and a number of modules are required for the developed symmetric security systems to ensure the same security level as the largest length key of the AES algorithm does. It is found that as the number of modules increases, their bitness decreases. Graphical dependencies of cryptoanalysis complexity on bitness and a number of modules are built. It is shown that with the increase of specified parameters, the cryptosecurity of the developed methods also increases.

Lattice-based cryptographic scheme is constructed based on hard problems on a lattice such as the short integer solution (SIS) problem and the learning with error (LWE). However, the cryptographic scheme based on SIS or LWE is inefficient since the size of the key is too large. Thus, most cryptographic schemes use the variants of LWE and SIS with ring and module structures. Albrecht and Deo showed that there is a reduction from module-LWE (M-LWE) to ring-LWE (R-LWE) in the polynomial ring (Asiacrypt 2017) by handling the error rate and modulus. However, unlike the LWE problem, the SIS problem does not have an error rate, but there is the upper bound $\beta$ on the norm of the solution of the SIS problem. In this paper, we propose the two novel reductions related to module-SIS (M-SIS) and ring-SIS (R-SIS) on a polynomial ring. We propose (i) the reduction from R-SIS$_{q^{k},m^{k},\beta^{k}}$ to R-SIS$_{q,m,\beta}$ and (ii) the reduction from M-SIS to R-SIS under norm constraint of R-SIS. Combining these two results implies that R-SIS for a specified modulus and number samples is more difficult than M-SIS under norm constraints of R-SIS, which provides the range of possible module ranks for M-SIS.

Modern attribute-based anonymous credential (ABC) systems benefit from special encodings that yield expressive and highly efficient show proofs on logical statements. The technique was first proposed by Camenisch and Groß, who constructed an SRSA-based ABC system with prime-encoded attributes that offers efficient AND, OR and NOT proofs. While other ABC frameworks have adopted constructions in the same vein, the Camenisch-Groß ABC has been the most expressive and asymptotically most efficient proof system to date, even if it was constrained by the requirement of a trusted message-space setup and an inherent restriction to finite-set attributes encoded as primes. In this paper, combining a new set commitment scheme and a SDH-based signature scheme, we present a provably secure ABC system that supports show proofs for complex statements. This construction is not only more expressive than existing approaches, it is also highly efficient under unrestricted attribute space due to its ECC protocols only requiring a constant number of bilinear pairings by the verifier; none by the prover. Furthermore, we introduce strong security models for impersonation and unlinkability under adaptive active and concurrent attacks to allow for the expressiveness of our ABC as well as for a systematic comparison to existing schemes. Given this foundation, we are the first to comprehensively formally prove the security of an ABC with expressive show proofs. Specifically, we prove the security against impersonation under the $q$-(co-)SDH assumption with a tight reduction. Besides the set commitment scheme, which may be of independent interest, our security models can serve as a foundation for the design of future ABC systems.

Various privacy-preserving protocols for exposure notification have been developed across the globe in order to aid in scaling contact tracing efforts during the COVID-19 crisis, a strategy proven to be critical in effectively slowing the spread of infectious disease. Although having a multitude of people working toward a similar goal creates momentum and aids in quality refinement, it also causes confusion for entities hoping to adopt one protocol for application development. This paper compares the protocols component-by-component, accumulating in a comprehensive comparison table so that entities are able to take action based on their priorities.

NewHope is a lattice cryptoscheme based on the Ring Learning With Errors (Ring-LWE) problem, and it has received much attention among the candidates of the NIST post-quantum cryptography standardization project. Recently, there have been key mismatch attacks on NewHope, where the adversary tries to recover the server’s secret key by observing the mismatch of the shared key from chosen queries. At CT-RSA 2019, Bauer et al. first proposed a key mismatch attack on NewHope, and then at ESORICS 2019, Qin et al. proposed an improved version with a success probability of 96.9% using about 880,000 queries. In this paper, we further improve their key mismatch attack on NewHope. First, we reduce the number of queries by adapting the terminating condition to the response from the server using an early abort technique. Next, the success rate of recovering the secret key polynomial is raised by considering the deterministic condition judging its coefficients. Furthermore, the search range of the secret key in Qin et al.’s attack is extended without increasing the number of queries. With the above improvements, to achieve an almost success rate of 97%, about 73% of queries can be reduced compared with Qin et al.’s method. Additionally, the success rate can be improved to 100.0%. In particular, we analyze the trade-off between the cost of queries and the success rate. We show that a lower success rate of 20.9% is available by further reduced queries of 135,000 simultaneously.

Inference using convolutional neural networks (CNNs) is often outsourced to the cloud for various applications. Hence it is crucial to detect the malfunction or manipulation of the inference results. To provide trustful services, the cloud services should prove that the inference results are correctly calculated with valid input data according to a legitimate model. Particularly, a resource-constrained client would prefer a small proof and fast verification. A pairing-based zero-knowledge Succinct Non-interactive ARgument of Knowledge(zk-SNARK) scheme is a useful cryptographic primitive that satisfies both the short-proof and quick-verification requirements with only black-box access to the models, irrespective of the function complexity. However, they require tremendous efforts for the proof generation. It is impractical to build a proof using traditional zk-SNARK approaches due to many (multiplication) operations in CNNs.

This paper proposes a new efficient verifiable convolution neural network (vCNN) framework, which allows a client to verify the correctness of the inference result rapidly with short evidence provided by an untrusted server. Notably, the proposed vCNNs framework is the first practical pairing-based zk-SNARK scheme for CNNs, and it significantly reduces space and time complexities to generate a proof with providing perfect zero-knowledge and computational knowledge soundness. The experimental results validate the practicality of vCNN with improving VGG16 performance and key size by 18000 fold compared with the existing zk-SNARKs approach (reducing the key size from 1400 TB to 80 GB, and proving time from 10 years to 8 hours).

PKC 2020 has been converted to a virtual conference this year, to be held June 1-4. The program is now live and registration is open. Chat will go live on Saturday, May 20. The only fees being collected are for the IACR membership, so if you already attended RWC or Eurocrypt this year, then you can register for free.

Event date: 19 October to 22 October 2020
Submission deadline: 22 June 2020
Notification: 22 July 2020

Job Description

We are looking for talented and experienced people to work as a Crypto. Systems Developer in Cryptographic Research and Development department.

Responsibilities

Design cryptographic solutions

Provide implementations in any required programming language.

Provide implementations for Web based, and Desktop applications.

Team work

Research and development in Cryptographic field

Education
Bachelor (or higher) degree in Computer Science or Computer Engineering or any related field.

Requirements

Good knowledge of Object Oriented Programming Languages, design patterns and principles.

An advanced knowledge in one of the following programming languages

Java, C++, C#

Some experience with C Programming Language

Good understanding of Digital Logic design.

Outstanding Grades in Math.

Excellent writing and speaking skills in English



Closing date for applications:

Contact: Please apply using the link.

More information: https://www.linkedin.com/jobs/view/1843094167

Our Junior Research Group program offers young scientists the opportunity to develop their own independent research program. We welcome applicants from all areas of security and privacy, including foundations, cryptography, software and hardware security, as well as human and other interdisciplinary aspects (e.g., computer science and psychology, economy, law, policy, ethics, etc). The positions are funded for 5 years. Applicants must have completed a doctoral degree in computer science or related areas and must have demonstrated outstanding research vision, and potential to successfully lead a research group. Successful candidates are expected to build a highly visible research agenda, to mentor Ph.D. students, and to participate in collaborative projects.

The Max Planck Institute for Security and Privacy (https://www.mpi-sp.org) is located in Bochum, Germany. We maintain an open, international, and diverse work environment and seek applications from outstanding researchers regardless of national origin. Our working language is English. We collaborate with several major research institutions worldwide and have high international visibility. We offer competitive salaries and support for Ph.D. students, as well as generous travel, administrative, and technical support.

Please apply at https://apply.cis.mpg.de/register/mpispjrgl

You need to upload your CV, a research plan, an optional teaching statement, and 3-5 references. Reviewing of applications will start immediately and will continue until the positions are filled. The expected starting date for the positions is Fall 2020, open to negotiations. Informal inquiries can be addressed to applications-jrgl@mpi-sp.org

Closing date for applications:

Contact: applications-jrgl@mpi-sp.org

More information: https://www.mpi-sp.org

TarGuess-I is a leading targeted password guessing model using users' personally identifiable information(PII) proposed at ACM CCS 2016 by Wang et al. Owing to its superior guessing performance, TarGuess-I has attracted widespread attention in password security. Yet, TarGuess-I fails to capture popular passwords and special strings in passwords correctly. Thus we propose TarGuess-I$ ^+ $: an improved password guessing model, which is capable of identifying popular passwords by generating top-300 most popular passwords from similar websites and grasping special strings by extracting continuous characters from user-generated PII. We conduct a series of experiments on 6 real-world leaked datasets and the results show that our improved model outperforms TarGuess-I by 9.07\% on average with 1000 guesses, which proves the effectiveness of our improvements.

To effectively trace the infection spread in a pandemic, a large number of manual contact tracers are required to reach out to all possible contacts of infected users. Exposure notification, a.k.a. digital contact tracing, can supplement manual contact tracing to ease the burden on manual tracers and to digitally obtain accurate contact information. We review the state-of-the-art solutions that offer security and privacy-friendly design. We study the role of policies and decision making to implement exposure notification and to protect user privacy. We then study how risk emerges in security, privacy, architecture, and technology aspects of exposure notification systems, and we wrap up with a discussion on architecture aspects to support these solutions.

In STOC 1988, Ben-Or, Goldwasser, and Wigderson (BGW) established an important milestone in the fields of cryptography and distributed computing by showing that every functionality can be computed with perfect (information-theoretic and error-free) security at the presence of an active (aka Byzantine) rushing adversary that controls up to $n/3$ of the parties.

We study the round complexity of general secure multiparty computation in the BGW model. Our main result shows that every functionality can be realized in only four rounds of interaction, and that some functionalities cannot be computed in three rounds. This completely settles the round-complexity of perfect actively-secure optimally-resilient MPC, resolving a long line of research.

Our lower-bound is based on a novel round-reduction technique that allows us to lift existing three-round lower-bounds for verifiable secret sharing to four-round lower-bounds for general MPC. To prove the upper-bound, we develop new round-efficient protocols for computing degree-2 functionalities over large fields, and establish the completeness of such functionalities. The latter result extends the recent completeness theorem of Applebaum, Brakerski and Tsabary (TCC 2018, Eurocrypt 2019) that was limited to the binary field.

Cryptocurrency light- or simplified payment verification (SPV) clients allow nodes with limited resources to efficiently verify execution of payments. Instead of downloading the entire blockchain, only block headers and selected transactions are stored. Still, the storage and bandwidth cost, linear in blockchain size, remain non-negligible, especially for smart contracts and mobile devices: as of April 2020, these amount to 50 MB in Bitcoin and 5 GB in Ethereum.

Recently, two improved sublinear light clients were proposed: to validate the blockchain, NIPoPoWs and FlyClient only download a polylogarithmic number of block headers, sampled at random. The actual verification of payments, however, remains costly: for each verified transaction, the corresponding block must too be downloaded. This yields NIPoPoWs and FlyClient only effective under low transaction volumes.

We present TxChain, a novel mechanism to maintain efficiency of light clients even under high transaction volumes. Specifically, we introduce the concept of contingent transaction aggregation, where proving inclusion of a single contingent transaction implicitly proves that $n$ other transactions exist in the blockchain. TxChain reduces the transaction verification overhead of (sublinear) light clients from $O(n)$ to $O(1)$ in the best and $O(n/c + log_c(n))$ in the worst case, for a blockchain constant $c$. We deploy TxChain on Bitcoin without consensus changes and implement a soft fork for Ethereum. Finally, we demonstrate effectiveness in the cross-chain setting: we implement TxChain as a smart contract on Ethereum to efficiently verify Bitcoin payments.

A decentralized funding system that supports companies of online products through mining cryptocurrencies and which renders mining pools benign. Working in tandem with blockchain cryptocurrencies, the system utilizes a user’s computing power to mine cryptocurrencies and future blockchain technologies. The system mines cryptocurrencies through a machine’s hardware during periods of low usage from the user. The blockchain payments received from the mining will be divvied between the services the user accesses via a percentage of use. A layer of blockchain technology is added to authenticate companies of online products and confirm the wallets of these companies. Each block contains the online service wallet’s public key for approved cryptocurrencies, a form of communication, and a DNS to confirm transmissions to the correct online service. After widespread adoption, disputes of DNS registration will result in the oldest block being the legitimate owner. Online services registered would be responsible for updating the blockchain. As the decentralized network of machines grows, the threat of manipulation through the 51% attack decreases as large mining pools lose the percentage of mining they have.