International Association
for Cryptologic Research

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.

Blockchain interoperability, which allows state transitions across different blockchain networks, is critical functionality to facilitate major blockchain adoption. Existing interoperability protocols mostly focus on atomic token exchange between blockchains. However, as blockchains have been upgraded from passive distributed ledgers into programmable state machines (thanks to smart contracts), the scope of blockchain interoperability goes beyond just token exchange. In this paper, we present HyperService, the first platform that delivers interoperability and programmability across heterogeneous blockchains. HyperService is powered by two innovative designs: (i) a developer-facing programming framework that allows developers to build cross-chain applications in a unified programming model; and (ii) a secure blockchain-facing cryptography protocol that provably realizes those applications on blockchains. We implement a prototype of HyperService in approximately 35,000 lines of code to demonstrate its practicality. Our experiment results show that (i) HyperService imposes reasonable latency, in order of seconds, on the end-to-end execution of cross-chain applications; (ii) the HyperService platform is scalable to continuously incorporate additional production blockchains

We construct new functional encryption schemes that combine the access control functionality of attribute-based encryption with the possibility of performing linear operations on the encrypted data. While such a primitive could be easily realized from fully fledged functional encryption schemes, what makes our result interesting is the fact that our schemes simultaneously achieve all the following properties. They are public-key, efficient and can be proved secure under standard and well established assumptions (such as LWE or pairings). Furthermore, security is guaranteed in the setting where adversaries are allowed to get functional keys that decrypt the challenge ciphertext. Our first results are two functional encryption schemes for the family of functions that allow users to embed policies (expressed by monotone span programs) in the encrypted data, so that one can generate functional keys to compute weighted sums on the latter. Both schemes are pairing-based and quite generic: they combine the ALS functional encryption scheme for inner products from Crypto 2016 with any attribute-based encryption schemes relying on the dual-system encryption methodology. As an additional bonus, they yield simple and elegant multi-input extensions essentially for free, thereby broadening the set of applications for such schemes. Multi-input is a particularly desirable feature in our setting, since it gives a finer access control over the encrypted data, by allowing users to associate different access policies to different parts of the encrypted data. Our second result builds identity-based functional encryption for inner products from lattices. This is achieved by carefully combining existing IBE schemes from lattices with adapted, LWE-based, variants of ALS. We point out to intrinsic technical bottlenecks to obtain richer forms of access control from lattices. From a conceptual point of view, all our results can be seen as further evidence that more expressive forms of functional encryption can be realized under standard assumptions and with little computational overhead.

We will discuss the question of minimizing different complexity measures of cryptographic primitives, some known results and remaining challenges, and how the study of this question can have impact beyond cryptography.

An aggregate signature allows one to generate a short aggregate of signatures from different signers on different messages. A sequential aggregate signature (SeqAS) scheme allows the signers to aggregate their individual signatures in a sequential manner. All existing SeqAS schemes that do not use the random oracle assumption either require a large public key or the security depends upon some non-standard interactive/static assumptions. In this paper, we present an efficient SeqAS scheme with constant-size public key under the SXDH assumption. In the process, we first obtain an optimized (and more efficient) variant of Libert et al's randomizable signature scheme. While both the schemes are more efficient than the currently best ones that rely on some static assumption, they are only slightly costlier than the most efficient ones based on some interactive assumption.

Contract fraud is a big nuisance in our society. People are scammed largely because of vague language used in contracts, which can cause misunderstandings. Therefore, people will seek professional help to review over ambiguous terms, especially, when signing a big contract, for example, leasing or buying property. With the advent of Ethereum blockchain, a new type of contract, named smart contract, is emerging nowadays, enabling people to describe a complicated logic as an automatically executable computer program. However, due to the lack of the computer background and software development experience, many people have difficulty in understanding blockchain-based smart contracts, which is adverse to the popularization of Ethereum. It has resulted in a new wave of contract fraud caused by smart contracts, which are self-executing and self-enforcing but also hard to understand by people. To fill this huge gap, we propose an approach to enable people without computer background to understand and operate Ethereum smart contracts. In doing so, smart contract fraud can be deterred if people have a better understanding of contract terms. Particularly, we investigate the general rules of the smart contract code, and build a novel tool named SMTranslator to automatically generate readable document. SMTranslator first translates smart contracts into standard structured files and identifies the core statement of each function in smart contracts. By exploiting the custom natural language generation, we generate the documents for smart contracts that can provide correct and understandable descriptions. We collect numerous contracts in Ethereum and select a number of typical contracts to conduct the experiments. Extensive experimental results demonstrate the feasibility and effectiveness of our approach.

Homomorphic Encryption is an elegant cryptographic solution to protect the privacy of users while keeping the conveniences of cloud computing. Using homomorphic encryption, users can upload their encrypted data to the cloud and can still perform computation on the encrypted data.

Applications are invited for one postdoc position in designing hardware architectures for accelerating homomorphic computing on the encrypted data. The researcher will perform algorithmic optimizations, design optimized hardware architectures, and explore the design-space to construct efficient homomorphic encryption processors on FPGA platforms.

Please apply to the official application portal before 1st June 2020.

More information: https://bham.taleo.net/careersection/external/jobdetail.ftl?job=200001O8&tz=GMT%2B01%3A00&tzname=Europe%2FLondon

Closing date for applications:

Contact: Dr. Sujoy Sinha Roy

More information: https://bham.taleo.net/careersection/external/jobdetail.ftl?job=200001O8&tz=GMT%2B01%3A00&tzname=Europe%2FLondon