International Association
for Cryptologic Research

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.

We present a novel $\textit{secure search}$ protocol on data and queries encrypted with Fully Homomorphic Encryption (FHE).

Our protocol enables organizations (client) to (1) securely upload an unsorted data array $x=(x[1],\ldots,x[n])$ to an untrusted honest-but-curious sever, where data may be uploaded over time and from multiple data-sources; and (2) securely issue repeated search queries $q$ for retrieving the first element $(i^*,x[i^*])$ satisfying an agreed matching criterion $i^* = \min\ \left\{ \left.i\in[n] \;\right\vert \mathsf{IsMatch}(x[i],q)=1 \right\}$, as well as fetching the next matching elements with further interaction.

For security, the client encrypts the data and queries with FHE prior to uploading, and the server processes the ciphertexts to produce the result ciphertext for the client to decrypt.

Our secure search protocol improves over the prior state-of-the-art for secure search on FHE encrypted data (Akavia, Feldman, Shaul (AFS), CCS'2018) in achieving:

(1) $\textit{Post-processing free}$ protocol where the server produces a ciphertext for the correct search outcome with overwhelming success probability.This is in contrast to returning a list of candidates for the client to post-process, or suffering from a noticeable error probability, in AFS. Our post-processing freeness enables the server to use secure search as a sub-component in a larger computation without interaction with the client.

(2) $\textit{Faster protocol:}$(a) Client time and communication bandwidth are improved by a $\log^2n/\log\log n$ factor. (b) Server evaluates a polynomial of degree linear in $\log n$ (compare to cubic in AFS), and overall number of multiplications improved by up to $\log n$ factor.(c) Employing only $\textrm{GF}(2)$ computations (compare to $\textrm{GF}(p)$ for $p \gg 2$ in AFS) to gain both further speedup and compatibility to all current FHE candidates.

(3) $\textit{Order of magnitude speedup exhibited by extensive benchmarks}$ we executed on identical hardware for implementations of ours versus AFS's protocols.

Additionally, like other FHE based solutions, out solution is setup-free: to outsource elements from the client to the server, no additional actions are performed on $x$ except for encrypting it element by element (each element bit by bit) and uploading the resulted ciphertexts to the server.

The discrete Gaussian sampler is one of the fundamental tools in implementing lattice-based cryptosystems. However, a naive discrete Gaussian sampling implementation suffers from side-channel vulnerabilities, and the existing countermeasures usually introduce significant overhead in either the running speed or the memory consumption.

In this paper, we propose a fast, compact, and constant-time implementation of the binary sampling algorithm, originally introduced in the BLISS signature scheme. Our implementation adapts the Renyi divergence and the transcendental function polynomial approximation techniques. The efficiency of our scheme is independent of the standard deviation, and we show evidence that our implementations are either faster or more compact than several existing constant-time samplers. In addition, we show the performance of our implementation techniques applied to and integrated with two existing signature schemes: qTesla, and Falcon. On the other hand, the convolution theorems are typically adapted to sample from larger standard deviations, by combining samples with much smaller standard deviations. As an additional contribution, we show better parameters for the convolution theorems.

The Key Assignment Scheme (KAS) is a well-studied cryptographic primitive used for hierarchical access control (HAC) in a multilevel organisation where the classes of people with higher privileges can access files of those with lower ones. Our first contribution is the formalization of a new cryptographic primitive, namely, KAS-AE that supports the aforementioned HAC solution with an additional authenticated encryption property. Next, we present three efficient KAS-AE schemes that solve the HAC and the associated authenticated encryption problem more efficiently -- both with respect to time and memory -- than the existing solutions that achieve it by executing KAS and AE separately. Our first KAS-AE construction is built by using the cryptographic primitive MLE (EUROCRYPT 2013) as a black box; the other two constructions (which are the most efficient ones) have been derived by cleverly tweaking the hash function FP (Indocrypt 2012) and the authenticated encryption scheme APE (FSE 2014). This high efficiency of our constructions is critically achieved by using two techniques: design of a mechanism for reverse decryption used for reduction of time complexity, and a novel key management scheme for optimizing storage requirements when organizational hierarchy forms an arbitrary access graph (instead of a linear graph). We observe that constructing a highly efficient KAS-AE scheme using primitives other than MLE, FP and APE is a non-trivial task. We leave it as an open problem. Finally, we provide a detailed comparison of all the KAS-AE schemes.

The security of web communication via the SSL/TLS protocols relies on safe distributions of public keys associated with web domains in the form of $\mathsf{X.509}$ certificates. Certificate authorities (CAs) are trusted third parties that issue these certificates. However, the CA ecosystem is fragile and prone to compromises. Starting with Google's Certificate Transparency project, a number of research works have recently looked at adding transparency for better CA accountability, effectively through public logs of all certificates issued by certification authorities, to augment the current $\mathsf{X.509}$ certificate validation process into SSL/TLS.

In this paper, leveraging recent progress in blockchain technology, we propose a novel system, called $\mathsf{CTB} $, that makes it impossible for a CA to issue a certificate for a domain without obtaining consent from the domain owner. We further make progress to equip $\mathsf{CTB}$ with certificate revocation mechanism. We implement $\mathsf{CTB}$ using IBM's Hyperledger Fabric blockchain platform. $\mathsf{CTB}$'s smart contract, written in Go, is provided for complete reference.