International Association
for Cryptologic Research

Multi-key fully homomorphic encryption (MKFHE) allows computations on ciphertexts encrypted by different users (public keys), and the results can be jointly decrypted using the secret keys of all the users involved. The NTRU-based scheme is an important alternative to post-quantum cryptography, but the NTRU-based MKFHE has the following drawbacks, which cause it inefficient in scenarios such as secure multi-party computing (MPC). One is the relinearization technique used for key switching takes up most of the time of the scheme’s homomorphic evaluation, the other is that each user needs to decrypt in sequence, which makes the decryption process complicated. We propose an efficient leveled MKFHE scheme, which improves the efficiency of homomorphic evaluations, and constructs a two-round (MPC) protocol based on this. Firstly, we construct an efficient single key FHE with less relinearization operations. We greatly reduces the number of relinearization operations in homomorphic evaluations process by separating the homomorphic multiplication and relinearization techniques. Furthermore, the batching technique and a specialization of modulus can be applied to our scheme to improve the efficiency. Secondly, the efficient single-key homomorphic encryption scheme proposed in this paper is transformed into a multi-key vision according to the method in LTV12 scheme. Finally, we construct a distributed decryption process which can be implemented independently for all participating users, and reduce the number of interactions between users in the decryption process. Based on this, a two-round MPC protocol is proposed. Experimental analysis shows that the homomorphic evaluation of the single-key FHE scheme constructed in this paper is 2.4 times faster than DHS16, and the MKFHE scheme constructed in this paper can be used to implement a two-round MPC protocol effectively, which can be applied to secure MPC between multiple users under the cloud computing environment.

We construct non-interactive zero-knowledge (NIZK) arguments for $\mathsf{NP}$ from any circular-secure fully homomorphic encryption (FHE) scheme. In particular, we obtain such NIZKs under a circular-secure variant of the learning with errors (LWE) problem while only assuming a standard (poly/negligible) level of security. Our construction can be modified to obtain NIZKs which are either: (1) statistically zero-knowledge arguments in the common random string model or (2) statistically sound proofs in the common reference string model.

We obtain our result by constructing a new correlation-intractable hash family [Canetti, Goldreich, and Halevi, JACM~'04] for a large class of relations, which suffices to apply the Fiat-Shamir heuristic to specific 3-message proof systems. In particular, assuming circular secure FHE, our hash function $h$ ensures that for any function $f$ of some a-priori bounded circuit size, it is hard to find an input $x$ such that $h(x)=f(x)$. This continues a recent line of works [Holmgren and Lombardi, FOCS~'18; Canetti et al., ePrint~'18] focused on instantiating special forms of correlation intractability and Fiat-Shamir under weaker assumptions. Another consequence of our hash family construction is that, assuming circular-secure FHE, the classic quadratic residuosity protocol of [Goldwasser, Micali, and Rackoff, SICOMP~'89] is not zero knowledge when repeated in parallel.

We also show that, under the plain LWE assumption (without circularity), our hash family is a universal correlation intractable family for general relations, in the following sense: If there exists any hash family of some description size that is correlation-intractable for general (even inefficient) relations, then our specific construction (with a comparable size) is correlation-intractable for general (efficiently verifiable) relations.

Security and privacy are paramount in the field of intelligent transportation systems (ITS). This motivates many proposals aiming to create a Vehicular Public Key Infrastructure (VPKI) for managing vehicles’ certificates. Among them, the Security Credential Management System (SCMS) is one of the leading contenders for standardization in the US. SCMS provides a wide array security features, which include (but are not limited to) data authentication, vehicle privacy and revocation of misbehaving vehicles. In addition, the key provisioning process in SCMS is realized via the so-called \emph{butterfly key expansion}, which issues arbitrarily large batches of pseudonym certificates in response to a single client request. Although promising, this process is based on classical elliptic curve cryptography (ECC), which is known to be susceptible to quantum attacks. Aiming to address this issue, in this work we propose a post-quantum \emph{butterfly key expansion} process. The proposed protocol relies on lattice-based cryptography, which leads to competitive key, ciphertext and signature sizes. Moreover, it provides low bandwidth utilization when compared with other lattice-based schemes, and, like the original SCMS, addresses the security and functionality requirements of vehicular communication.

The abundance of smart devices and sensors has given rise to an unprecedented large-scale data collection. While this benefits various data-driven application domains, it raises numerous security and privacy concerns. In particular, recent high-profile data breach incidents demonstrate security dangers and single point vulnerability of multiple systems. Moreover, even if the data is properly protected at rest (i.e., during storage), data confidentiality may still be compromised once it is fed as input to computations. In this paper, we introduce Senopra, a privacy-preserving data management framework that leverages trusted execution environment and confidentiality-preserving smart contract system to empower data owners with absolute control over their data. More specifically, the data owners can specify fine-grained access policies governing how their captured data is accessed. The access policies are then enforced by a policy agent that operates in an autonomous and confidentiality-preserving manner. To attain scalability and efficiency, Senopra exploits Key Aggregation Cryptosystem (KAC) for key management, and incorporates an optimisation that significantly improves KAC's key reconstruction cost. Our experimental study shows that Senopra can support privacy- preserving data management at scale with low latency.

HEAAN is a homomorphic encryption (HE) scheme for approximate arithmetics. Its vector packing technique proved its potential in cryptographic applications requiring approximate computations, including data analysis and machine learning.

In this paper, we propose MHEAAN - a generalization of HEAAN to the case of a tensor structure of plaintext slots. Our design takes advantage of the HEAAN scheme, that the precision losses during the evaluation are limited by the depth of the circuit, and it exceeds no more than one bit compared to unencrypted approximate arithmetics, such as floating point operations. Due to the multi-dimensional structure of plaintext slots along with rotations in various dimensions, MHEAAN is a more natural choice for applications involving matrices and tensors. We provide a concrete two-dimensional construction and show the efficiency of our scheme on several matrix operations, such as matrix multiplication, matrix transposition, and inverse.

As an application, we implement the non-interactive Deep Neural Network (DNN) classification algorithm on encrypted data and encrypted model. Due to our efficient bootstrapping, the implementation can be easily extended to DNN structure with an arbitrary number of hidden layers

Registration is now open for FSE 2019; see https://fse.iacr.org/2019/registration.html. Early-bird discounts are in effect until Feb 26.

The conference will be held March 25-28 in Paris, France.

Dear members of the IACR

The year 2018 saw considerable growth for IACR: The first RWC sponsored by IACR took place in Zurich, attended by 600 people; the largest Crypto ever with 641 attendees, was held at UCSB in August; and the IACR counts a record number of more than 2100 members for the year 2019.

On behalf of everyone in the field, I'd like to thank the organizers of conferences, workshops, schools, and all further activities of the IACR, as well as the Board members and everyone else working behind the scene, for their efforts in making this possible.

As we move into 2019, let me mention some new developments.

Test-of-time award for the General Conferences

A new Test-of-time Award has been established recently and will start in 2019. It is given out yearly for each one of the three IACR General Conferences: Eurocrypt, Crypto, and Asiacrypt. The award honors "a paper with a lasting impact on the field" and will be given at the conference in year X to a paper published at the same conference in year X - 15.

The awards are selected by a yearly committee with five members, of which two members are appointed by Board and three are program chairs for the respective conferences in year X. This year's committee is chaired by Dan Boneh. Please see the details at https://iacr.org/testoftime/

Silvio Micali to hold the IACR Distinguished Lecture 2020

At its meeting in August, the Board has invited Silvio Micali to the hold the 2020 IACR Distinguished Lecture. This lecture is held annually and rotates between the three IACR General Conferences. We look forward to Silvio Micali's lecture at Crypto 2020!

For more information about the IACR Distinguished Lecture, see the website at https://iacr.org/publications/dl/

Board members

The IACR 2018 election was held in October/November to fill three of nine IACR Director positions. Congratulations to Michel Abdalla, Nadia Heninger, and Anna Lysyanskaya for being elected as directors! Michel and Anna were re-elected to their director positions and Nadia joins as a new director.

Among the incumbents of director positions, Phil Rogaway did not run for election and leaves the Board. Likewise the General Chairs of the 2019 General Conferences leave the Board and will again have more time to enjoy a conference as a guest: Orr Dunkelman, Tal Rabin, and Josef Pieprzyk. Let me thank all of them for their memorable contributions to the IACR!

Furthermore, Mitsuru Matsui has been elected as the chair of the Asiacrypt Steering Committee; this committee selects the venues for Asiacrypt as set forth in IACR's operational procedures (https://iacr.org/docs/steering.pdf). Thanks to Xuejia Lai for his work in this role until 2018.

Next IACR events

• Real World Crypto Symposium (RWC 2019), San Jose, USA, Jan 9 - Jan 11
• Fast Software Encryption (FSE 2019), Paris, France, Mar 25 - Mar 28
• Public Key Cryptography (PKC 2019), Beijing, China, Apr 14 - Apr 17
• Eurocrypt 2019, Darmstadt, Germany, May 19 - May 23

To find out more about your IACR and the work of the Board of Directors, please visit https://www.iacr.org and see the minutes of meeting at https://www.iacr.org/docs/minutes/

Happy New Year and best wishes for 2019!

Christian Cachin
IACR President

Applications are invited from the Indian nationals for the position of Junior Research Fellow (JRF) to work in the Interdisciplinary Cyber Physical Systems (ICPS) - DST funded research project entitled “FPGA prototype of non-recursive key based cryptosystem for secure transmission of real time privacy signal”. Selected candidate will also be encouraged for the registration in Ph.D. program as per Institute rules.

Post: Junior Research Fellow (JRF)

Number of Posts: 1

Project Duration: 3 years or till the completion of the project, whichever is earlier (the position is purely temporary in nature and performance will be reviewed periodically) extendable on approval of ICPS, DST as per ICPS guidelines.

Stipend: 25,000 per month and HRA as admissible depending upon merits, suitability, qualifications and as per the ICPS, DST guidelines.

Essential Qualifications:

BE/B.Tech/ME/M.Tech in Electronics and Communication / VLSI / Computer Science / Information Technology or any other related subject with minimum CPI of 5.5 or 55% marks aggregate in the last degree.

Candidates having good academic and research background with GATE Qualification will be given preference.

Desirables: Candidates having knowledge of Communication/ FPGA (VHDL/Verilog) / Xilinx / Cryptography will be preferred.

Selection Procedure: Written Test (if found desirable by the selection committee) and Interview

How to Apply?

Completely filled application form along with detailed Biodata may be sent by e-mail to soundra.pandiankk (at) gmail.com and the hard copy to be brought on the date of interview. Please note that no TA/DA will be given to the candidates called for the interview.

Incomplete application or only CV shall not be entertained.

Last date for receipt of applications by email: January 31, 2019. Please note that the list of shortlisted candidates and date of interview shall be notified on the web portal after January 31, 2019.

Closing date for applications: 31 January 2019

Contact: Contact: Principal Investigator (PI)

Dr. K.K. Soundra Pandian

Department of Electronics and Communication, VLSI - Cryptography

Indian Institute of Information Technology Design & Manufacturing (IIITDM) Jabalpur

Dumna Airport Road, P.O. Khamaria,

Jabalpur-482005, Madhya Pradesh

Tel: (O): +91-0761-2794473

(M): +91-94446-08310

More information: https://www.iiitdmj.ac.in

The positions are offered within the A-WEAR European Joint Doctorate action of the highly appreciated EU-funded Marie Sk?odowska Curie grants. We offer high-class training and the possibility of PhD graduation with double or joint PhD certificate. The positions are fully funded for a 36-month period.

Tasks and objectives: Design and evaluate novel cryptographic technologies for the protection of privacy and digital identity of electronic users, in particular those providing attribute-based authentication in electronic systems; Ensure the user authenticity in dynamic wireless wearable architectures; Find solutions to solve the inefficient revocation of invalid users, the missing identification of malicious users and low performance on constrained devices, such as wearables; Test and benchmark the developed algorithms on existing wearable hardware devices, such as personal tags, smart watch, smart cards.

Closing date for applications: 28 February 2019

Contact: https://euraxess.ec.europa.eu/jobs/364125

More information: http://www.tut.fi/a-wear/recruitment/ESR13.pdf

The Cryptanalysis Taskforce research group at Nanyang Technological University in Singapore is seeking for candidates to fill one (senior) research fellow position (from fresh postdoc to senior researchers). The team focuses its research on symmetric-key cryptography, including but not limited to provable security, cryptanalysis, and design.

NTU Singapore offers globally competitive salary package with extremely low income tax and an excellent environment for research. The contract will be initially for one-year, and has the possibility to be extended subject to the performance and availability of funding. The position will be open until filled, interested candidates are to send their CV and 2 reference letters to Prof. Jian Guo. Further information about the research group can be found here: http://catf.crypto.sg

Closing date for applications: 31 May 2019

Contact: Jian Guo, Assistant Professor, guojian (at) ntu.edu.sg

While standard encryption guarantees secrecy of the encrypted plaintext only against an attacker that has no knowledge of the communicating parties’ keys and randomness of encryption, deniable encryption [Canetti et al., Crypto’96] provides the additional guarantee that the plaintext remains secret even in face of authoritative entities that attempt to coerce (or bribe) communicating parties to expose their internal states, including the plaintexts, keys and randomness. To achieve this guarantee, deniable encryption is equipped with a faking algorithm which allows parties to generate fake keys and randomness that make the ciphertext appear consistent with any plaintext of the parties’ choice.

To date, only partial results were known: either deniability against coercing only the sender, or against coercing only the receiver [Sahai-Waters, STOC ‘14] or schemes satisfying weaker notions of deniability [O’Neil et al., Crypto ‘11].

In this paper we present the first fully bideniable interactive encryption scheme, thus resolving the 20-years-old open problem. Our scheme also satisfies an additional, incomparable to standard deniability, property called off-the-record deniability, which we introduce in this paper. This property guarantees that, even if the sender claims that one plaintext was used and the receiver claims a different one, the adversary has no way of figuring out who is lying - the sender, the receiver, or both. This is useful when parties don’t have means to agree on what fake plaintext to claim, or when one party defects against the other.

Our protocol has three messages, which is optimal [Bendlin et al., Asiacrypt’11], and works in a CRS model. We assume subexponential indistinguishability obfuscation (iO) and one way functions.

In relay attacks,a man-in-the-middle attacker gains access to a service by relaying the messages between two legitimate parties. Distance-bounding protocols are a countermeasure to relay attacks, whereby a verifier measures the round-trip time in exchanges with a prover.

Inspired by application-security definitions, we propose a new security model, OracleDB, distinguishing two prover-corruption types: black-box and white-box.

We use this distinction to settle the long-lasting arguments about terrorist-fraud resistance, by showing that it is irrelevant in both the black-box and white-box corruption models.

We then exhibit a security flaw in the PayPass protocol with relay protection, used in EMV contactless payments. We propose an extension to this industry-standard protocol, with only small modifications, and prove its security in our strongest adversary model.

Finally, we exhibit a new generalised distance-fraud attack strategy that defeats the security claims of at least 12 existing distance-bounding protocols.

Recent papers show how to construct polynomial invariant attacks for block ciphers, however almost all such results are somewhat weak: invariants are simple and low degree and the Boolean functions tend by very simple if not degenerate. Is there a better more realistic attack, with invariants of higher degree and which is likely to work with stronger Boolean functions? In this paper we show that such attacks exist and can be constructed explicitly through on the one side, the study of Fundamental Equation of eprint/2018/807, and on the other side, a study of the space of Annihilators of any given Boolean function. Our approach is suitable for backdooring a block cipher in presence of an arbitrarily strong Boolean function not chosen by the attacker. The attack is constructed using excessively simple paper and pencil maths.

Accumulators, first introduced by Benaloh and de Mare (Eurocrypt 1993), are compact representations of arbitrarily large sets and can be used to prove claims of membership or non-membership about the underlying set. They are almost exclusively used as building blocks in real-world complex systems, including anonymous credentials, group signatures and, more recently, anonymous cryptocurrencies. Having rigorous security analysis for such systems is crucial for their adoption and safe use in the real world, but it can turn out to be extremely challenging given their complexity. In this work, we provide the first universally composable (UC) treatment of cryptographic accumulators. There are many different types of accumulators: some support additions, some support deletions and some support both; and, orthogonally, some support proofs of membership, some support proofs of non-membership, and some support both. Our UC definition covers all of these types of accumulators concisely in a single functionality, and captures the two basic security properties of accumulators: correctness and soundness. We then prove the equivalence of our UC definition to standard accumulator definitions. This implies that existing popular accumulator schemes, such as the RSA accumulator, already meet our UC definition, and that the security proofs of existing systems that leverage such accumulators can be significantly simplified. Finally, we use our UC definition to get simple proofs of security. We build an accumulator in a modular way out of two weaker accumulators (in the style of Baldimtsi et al. (Euro S&P 2017), and we give a simple proof of its UC security. We also show how to simplify the proofs of security of complex systems such as anonymous credentials using our UC definition.

Imagine if, given a puzzle, you could encrypt a plaintext detailing the location of a prize reward such that he who solves the puzzle can use this solution to decrypt our prize information, without knowing the solution to the puzzle yourself.

The Jevil family of encryption systems is a novel set of real-world encryption systems based on the promising foundation of witness encryption. The first Jevil encryption systems comprise of Pentomino and Sudoku-based encryption, allowing for the encryption of plaintext such that solving a Pentomino or Sudoku puzzle yields to decryption. Jevil encryption systems are shown to be correct, secure and to achieve high performance with modest overhead.

Sidechains have long been heralded as the key enabler of blockchain scalability and interoperability. However, no modeling of the concept or a provably secure construction has so far been attempted.

We provide the first formal definition of what a sidechain system is and how assets can be moved between sidechains securely. We put forth a security definition that augments the known transaction ledger properties of persistence and liveness to hold across multiple ledgers and enhance them with a new ``firewall'' security property which safeguards each blockchain from its sidechains, limiting the impact of an otherwise catastrophic sidechain failure.

We then provide a sidechain construction that is suitable for proof-of-stake (PoS) sidechain systems. As an exemplary concrete instantiation we present our construction for an epoch-based PoS system consistent with Ouroboros (Crypto~2017), the PoS blockchain protocol used in Cardano which is one of the largest pure PoS systems by market capitalisation, and we also comment how the construction can be adapted for other protocols such as Ouroboros Praos (Eurocrypt~2018), Ouroboros Genesis (CCS~2018), Snow White and Algorand. An important feature of our construction is {\em merged-staking} that prevents ``goldfinger'' attacks against a sidechain that is only carrying a small amount of stake. An important technique for pegging chains that we use in our construction is cross-chain certification which is facilitated by a novel cryptographic primitive we introduce called ad-hoc threshold multisignatures (ATMS) which may be of independent interest. We show how ATMS can be securely instantiated by regular and aggregate digital signatures as well as succinct arguments of knowledge such as STARKs and bulletproofs with varying degrees of storage efficiency.

Memory-constrained devices, including widely used smart cards, require resisting attacks by the quantum computers. Lattice-based encryption scheme possesses high efficiency and reliability which could run on small devices with limited storage capacity and computation resources such as IoT sensor nodes or smart cards. We present the first implementation of a lattice-based encryption scheme on the standard Java Card platform by combining number theoretic transform and improved Montgomery modular multiplication. The running time of decryption is nearly optimal (about 7 seconds for 128-bit security level). We also optimize discrete Ziggurat algorithm and Knuth-Yao algorithm to sample from prescribed probability distributions on the Java Card platform. More importantly, we indicate that polynomial multiplication can be performed on Java Card efficiently even if the long integers are not supported, which makes running more lattice-based cryptosystems on smart cards achievable.

We present a general framework for representing cryptographic protocols and analyzing their security. The framework allows specifying the security requirements of practically any cryptographic task in a unified and systematic way. Furthermore, in this framework the security of protocols is maintained under a general protocol composition operation, called universal composition. The proposed framework with its security-preserving composition property allow for modular design and analysis of complex cryptographic protocols from relatively simple building blocks. Moreover, within this framework, protocols are guaranteed to maintain their security within any context, even in the presence of an unbounded number of arbitrary protocol instances that run concurrently in an adversarially controlled manner. This is a useful guarantee, that allows arguing about the security of cryptographic protocols in complex and unpredictable environments such as modern communication networks.

We develop attacks on the security of variants of pseudo-random generators computed by quadratic polynomials. In particular we give a general condition for breaking the one-way property of mappings where every output is a quadratic polynomial (over the reals) of the input. As a corollary, we break the degree-2 candidates for security assumptions recently proposed for constructing indistinguishability obfuscation by Ananth, Jain and Sahai (ePrint 2018) and Agrawal (ePrint 2018). We present conjectures that would imply our attacks extend to a wider variety of instances, and in particular offer experimental evidence that they break assumption of Lin-Matt (ePrint 2018).

Our algorithms use semidefinite programming, and in particular, results on low-rank recovery (Recht, Fazel, Parrilo 2007) and matrix completion (Gross 2009).

In 1994, Feige, Kilian, and Naor proposed a simple protocol for secure $3$-way comparison of integers $a$ and $b$ from the range $[0,2]$. Their observation is that for $p=7$, the Legendre symbol $(x | p)$ coincides with the sign of $x$ for $x=a-b\in[-2,2]$, thus reducing secure comparison to secure evaluation of the Legendre symbol. More recently, in 2011, Yu generalized this idea to handle secure comparisons for integers from substantially larger ranges $[0,d]$, essentially by searching for primes for which the Legendre symbol coincides with the sign function on $[-d,d]$.

In this paper, we present new comparison protocols based on the Legendre symbol that additionally employ some form of error correction. We relax the prime search by requiring that the Legendre symbol encodes the sign function in a noisy fashion only. Practically, we use the majority vote over a window of $2k+1$ adjacent Legendre symbols, for small positive integers $k$. Our technique significantly increases the comparison range: e.g., for a modulus of $60$ bits, $d$ increases by a factor of $2.9$ (for $k=1$) and $5.4$ (for $k=2$) respectively. We give a practical method to find primes with suitable noisy encodings.

We demonstrate the practical relevance of our comparison protocol by applying it in a secure neural network classifier for the MNIST dataset. Concretely, we discuss a secure multiparty computation based on the binarized multi-layer perceptron of Hubara et al., using our comparison for the second and third layers.