International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News

Here you can see all recent updates to the IACR webpage. These updates are also available:

email icon
via email
RSS symbol icon
via RSS feed

25 February 2020

Rishiraj Bhattacharyya, Mridul Nandi, Anik Raychaudhuri
ePrint Report ePrint Report
In CRYPTO 2018, Russell et al. introduced the notion of crooked indifferentiability to analyze the security of a hash function when the underlying primitive is subverted. They showed that the $n$-bit to $n$-bit function implemented using enveloped XOR construction ($\mathsf{EXor}$) with $3n+1$ many $n$-bit functions and $3n^2$- bit random initial vectors (iv) can be proven secure asymptotically in the crooked indifferentiability setting.

-We identify several major issues and gaps in the proof by Russel et al. We show that their proof does not work when the adversary makes queries related to multiple messages or in the case of intricate function dependent subversion. -We formalize new technique to prove crooked indifferentiability for multiple messages. Our technique can handle function dependent subversion. We apply our technique to provide a concrete proof for the $\mathsf{EXor}$ construction.

-We analyze crooked indifferentiability of the classical sponge construction. We show, using a simple proof idea, the sponge construction is a crooked-indifferentiable hash function using only $n$-bit random iv.
Expand
Jing Tian, Jun Lin, Zhongfeng Wang
ePrint Report ePrint Report
Supersingular isogeny key encapsulation (SIKE) protocol delivers promising public and secret key sizes over other post-quantum candidates. However, the huge computations form the bottleneck and limit its practical applications. The modular multiplication operation, which is one of the most computationally demanding operations in the fundamental arithmetics, takes up a large part of the computations in the protocol. In this paper, we propose an improved unconventional-radix finite-field multiplication (IFFM) algorithm which reduces the computational complexity by about 20% compared to previous algorithms. We then devise a new high-speed modular multiplier architecture based on the IFFM. It is shown that the proposed architecture can be extensively pipelined to achieve a very high clock speed due to its complete feedforward scheme, which demonstrates significant advantages over conventional designs. The FPGA implementation results show the proposed multiplier has about 67 times faster throughput than the state-of-the-art designs and more than 12 times better area efficiency than previous works. Therefore, we think that these achievements will greatly contribute to the practicability of this protocol.
Expand
Xiaopeng Zhao, Zhenfu Cao, Xiaolei Dong, Jun Shao, Zhusen Liu
ePrint Report ePrint Report
Designing an efficient public-key cryptosystem supporting additive homomorphism is not an easy job. At Eurocrypt 2013, Joye and Libert proposed a method for generalizing the Goldwasser-Micali cryptosystem. Their work basically addressed the issue of the ciphertext expansion, which is quite large in the Goldwasser-Micali cryptosystem. In this paper, we generalize the quadratic residue theory to the cases of higher-power residue. We also provide some new efficient methods for computing a type of higher-power residue symbols, which gives a generic tool for constructing practical cryptographic schemes, protocols and systems. To illustrate this point, we utilize it to generalize and improve the Joye-Libert cryptosystem. We also generalize some well-known results on quadratic residue and use them to instantiate the subgroup indistinguishability assumption, which can be utilized to construct key-dependent security and auxiliary-input security schemes.
Expand
Andrea Basso, Péter Kutas, Simon-Philipp Merz, Christophe Petit, Charlotte Weitkämper
ePrint Report ePrint Report
The $k$-SIDH protocol is a static-static isogeny-based key agreement protocol. At Mathcrypt 2018, Jao and Urbanik introduced a variant of this protocol which uses non-scalar automorphisms of special elliptic curves to improve its efficiency. In this paper, we provide a new adaptive attack on Jao-Urbanik's protocol. The attack is a non-trivial adaptation of Galbraith-Petit-Shani-Ti's attack on SIDH (Asiacrypt 2016) and its extension to $k$-SIDH by Dobson-Galbraith-LeGrow-Ti-Zobernig (IACR eprint 2019). Our attack provides a speedup compared to a naïve application of Dobson et al.'s attack to Jao-Urbanik's scheme, exploiting its inherent structure. Estimating the security of $k$-SIDH and Jao-Urbanik's variant with respect to these attacks, $k$-SIDH provides better efficiency.
Expand
Benjamin Lipp
ePrint Report ePrint Report
Hybrid Public Key Encryption (HPKE) is a cryptographic primitive being standardized by the Crypto Forum Research Group (CFRG) within the Internet Research Task Force (IRTF). HPKE schemes combine asymmetric and symmetric cryptographic primitives for efficient authenticated encryption of arbitrary-sized plaintexts under a given recipient public key. This document presents a mechanized cryptographic analysis done with CryptoVerif, of all four HPKE modes, instantiated with a prime-order-group Diffie-Hellman Key Encapsulation Mechanism (KEM).
Expand
Zhihao Zheng, Jiachen Shen, Zhenfu Cao
ePrint Report ePrint Report
With the location-based services booming, the volume of spatial data inevitably explodes. In order to reduce local storage and computational overhead, users tend to outsource data and initiate queries to the cloud. However, sensitive data or queries may be compromised if cloud server has access to raw data and plaintext token. To cope with this problem, searchable encryption for geometric range is applied. Geometric range search has wide applications in many scenarios, especially the circular range search.

In this paper, we propose a practical and secure circular range search scheme (PSCS) to support searching for spatial data in a circular range. With Our scheme, a semi-honest cloud server will return the data for a given circular range correctly without revealing index privacy or query privacy. We propose a polynomial split algorithm which can decompose the inner product calculation neatly. Then, We formally define the security of our scheme and theoretically prove that it is secure under same-closeness-pattern chosen-plaintext attacks (CLS-CPA). In addition, we demonstrate the efficiency and accuracy through analysis and experiments compared with existing schemes.
Expand
Mihir Bellare, Hannah Davis, Felix Günther
ePrint Report ePrint Report
It is convenient and common for schemes in the random oracle model to assume access to multiple random oracles (ROs), leaving to implementations the task (we call it oracle cloning) of constructing them from a single RO. The first part of the paper is a case study of oracle cloning in KEM submissions to the NIST Post-Quantum Cryptography standardization process. We give key-recovery attacks on some submissions arising from mistakes in oracle cloning, and find other submissions using oracle cloning methods whose validity is unclear. Motivated by this, the second part of the paper gives a theoretical treatment of oracle cloning. We give a definition of what is an "oracle cloning method" and what it means for such a method to "work," in a framework we call read-only indifferentiability, a simple variant of classical indifferentiability that yields security not only for usage in single-stage games but also in multi-stage ones. We formalize domain separation, and specify and study many oracle cloning methods, including common domain-separating ones, giving some general results to justify (prove read-only indifferentiability of) certain classes of methods. We are not only able to validate the oracle cloning methods used in many of the unbroken NIST PQC KEMs, but also able to specify and validate oracle cloning methods that may be useful beyond that.
Expand
T-H. Hubert Chan, Kai-Min Chung, Wei-Kai Lin, Elaine Shi
ePrint Report ePrint Report
Massively Parallel Computation (MPC) is a model of computation widely believed to best capture realistic parallel computing architectures such as large-scale MapReduce and Hadoop clusters. Motivated by the fact that many data analytics tasks performed on these platforms involve sensitive user data, we initiate the theoretical exploration of how to leverage MPC architectures to enable efficient, privacy-preserving computation over massive data. Clearly if a computation task does not lend itself to an efficient implementation on MPC even without security, then we cannot hope to compute it efficiently on MPC with security. We show, on the other hand, that any task that can be efficiently computed on MPC can also be securely computed with comparable efficiency. Specifically, we show the following results: • any MPC algorithm can be compiled to a communication-oblivious counterpart while asymp- totically preserving its round and space complexity, where communication-obliviousness ensures that any network intermediary observing the communication patterns learn no information about the secret inputs; • assuming the existence of Fully Homomorphic Encryption with a suitable notion of compact- ness and other standard cryptographic assumptions, any MPC algorithm can be compiled to a secure counterpart that defends against an adversary who controls not only intermediate network routers but additionally up to 1/3 − η fraction of machines (for an arbitrarily small constant η) — moreover, this compilation preserves the round complexity tightly, and preserves the space complexity upto a multiplicative security parameter related blowup. As an initial exploration of this important direction, our work suggests new definitions and proposes novel protocols that blend algorithmic and cryptographic techniques.
Expand
Edimar Veríssimo
ePrint Report ePrint Report
Viktoria hash is a compression function that generates a set of 512 bits from an arbitrary size input (limit of 2^480-1 bytes). This hash function contains some internal routines clearly inspired by AES and RC4 symmetric algorithms [14]. The new paradigm presents two major innovations: a fast preprocessing that initiates an internal state of 256!^2 permutations and a post-processing that guarantees a minimum number of executed rounds of 2^13. The pre-processing allows to differentiate very similar messages in the first runs of the algorithm. In the post-processing we have a safety barrier provided by a large number of rounds through a different structure of the main processing. The Viktoria algorithm seems to inaugurate a new design model in the construction of robust hash functions for some reasons, among them we highlight: the customization of the internal state according to each message, the elegance and efficiency of its main function and also a supposed high margin of safety provided by its post-processing function. Viktoria hash can also process bit oriented messages (whose last byte size is not complete) and generate larger hashes (1024, 1536, 2048 or larger) always as multiples of 512.
Expand
Early registration deadline March 31st
PKC PKC
The IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC) 2020 will take place in in Edinburgh, Scotland on May 4-7 2020.

The registration site is now open. Please note that the early bird registration will end on March 31st. After that deadline, a late registration fee will be charged.

The list of accepted papers is posted here.
Expand

24 February 2020

Andrew Hone
ePrint Report ePrint Report
The Lyness map is a birational map in the plane which provides one of the simplest discrete analogues of a Hamiltonian system with one degree of freedom, having a conserved quantity and an invariant symplectic form. As an example of a symmetric Quispel-Roberts-Thompson (QRT) map, each generic orbit of the Lyness map lies on a curve of genus one, and corresponds to a sequence of points on an elliptic curve which is one of the fibres in a pencil of biquadratic curves in the plane.

We present a version of the elliptic curve method (ECM) for integer factorization, which is based on iteration of the Lyness map with a particular choice of initial data. More precisely, we give an algorithm for scalar multiplication of a point on an elliptic curve, which is represented by one of the curves in the Lyness pencil. In order to avoid field inversion, and require only field multiplication (M), squaring (S) and addition, projective coordinates in P^1 x P^1 are used. Neglecting multiplication by curve constants (assumed small), each addition of the chosen point uses 2M, while each doubling step requires 15M. We further show that the doubling step can be implemented efficiently in parallel with four processors, dropping the effective cost to 4M.

In contrast, the fastest algorithms in the literature, using twisted Edwards curves with small curve constants, use 8M for point addition and 4M+4S for point doubling, both of which can be run in parallel with four processors to yield effective costs of 2M and 1M+1S, respectively. Thus our scalar multiplication algorithm should require, on average, roughly twice as many multiplications per bit as state of the art methods using twisted Edwards curves, but it can be applied to any elliptic curve over Q, whereas twisted Edwards curves (equivalent to Montgomery curves) correspond to only a subset of all elliptic curves. Hence, if implemented in parallel, our method may have potential advantages for integer factorization or elliptic curve cryptography.
Expand
Céline Chevalier, Ehsan Ebrahimi, Quoc-Huy Vu
ePrint Report ePrint Report
Indistinguishability against adaptive chosen-ciphertext attacks (IND-CCA2) is usually considered the most desirable security notion for classical encryption. In this work, we investigate its adaptation in the quantum world, when an adversary can perform superposition queries. The security of quantum-secure classical encryption has first been studied by Boneh and Zhandry (CRYPTO'13), but they restricted the adversary to classical challenge queries, which makes the indistinguishability only hold for classical messages (IND-qCCA2). We extend their work by giving the first security notions for fully quantum indistinguishability under quantum adaptive chosen-ciphertext attacks, where the indistinguishability holds for superposition of plaintexts (qIND-qCCA2). This resolves an open problem asked by Gagliardoni et al. (CRYPTO'16).

The qCCA2 security is defined in Boneh-Zhandry's paper using string copying and comparison, which is inherent in the classical setting. Quantumly, it is unclear what it means for a ciphertext to be different from the challenge ciphertext, and how the challenger can check the equality. The classical approach would either violate the no-cloning theorem or lead to perturbing the adversary's state, which may be detectable. To remedy these problems, from the recent groundbreaking compressed oracle technique introduced by Zhandry (CRYPTO'19), we develop a generic framework that allows recording quantum queries for probabilistic functions. We then give definitions for fully quantum real-or-random indistinguishability under adaptive chosen-ciphertext attacks (qIND-qCCA2).

In the symmetric setting, we show that various classical modes of encryption are trivially broken in our security notions. We then provide the first formal proof for quantum security of the Encrypt-then-MAC paradigm, which also answers an open problem posed by Boneh and Zhandry.

In the public-key setting, we show how to achieve these stronger security notions (qIND-qCCA2) from any encryption scheme secure in the sense of Boneh-Zhandry (IND-qCCA2). Along the way, we also give the first definitions of non-malleability for classical encryption in the quantum world and show that the picture of the relations between these notions is essentially the same as in the classical setting.
Expand
Mridul Nandi
ePrint Report ePrint Report
In an early version of CRYPTO’17, Mennink and Neves pro- posed EWCDMD, a dual of EWCDM, and showed n-bit security, where n is the block size of the underlying block cipher. In CRYPTO’19, Chen et al. proposed permutation based design SoKAC21 and showed 2n/3- bit security, where n is the input size of the underlying permutation. In this paper we show birthday bound attacks on EWCDMD and SoKAC21, invalidating their security claims. Both attacks exploit an inherent com- position nature present in the constructions. Motivated by the above two attacks exploiting the composition nature, we consider some generic relevant composition based constructions of ideal primitives (possibly in the ideal permutation and random oracle model) and present birthday bound distinguishers for them. In particular, we demonstrate a birthday bound distinguisher against (1) a secret random permutation followed by a public random function and (2) composition of two secret random functions. Our distinguishers for SoKAC21 and EWCDMD are direct con- sequences of (1) and (2) respectively.
Expand
Vipul Goyal, Abhishek Jain, Zhengzhong Jin, and Giulio Malavolta
ePrint Report ePrint Report
We study the problem of achieving statistical privacy in interactive proof systems and oblivious transfer -- two of the most well studied two-party protocols -- when limited rounds of interaction are available. Statistical Zaps: We give the first construction of statistical Zaps, namely, two-round statistical witness-indistinguishable (WI) protocols with a public-coin verifier. Our construction achieves computational soundness based on the quasi-polynomial hardness of learning with errors.

Three-Round Statistical Receiver-Private Oblivious Transfer: We give the first construction of a three-round oblivious transfer (OT) protocol -- in the plain model -- that achieves statistical privacy for receivers and computational privacy for senders against malicious adversaries, based on polynomial-time assumptions. The round-complexity of our protocol is optimal.

We obtain our first result by devising a public-coin approach to compress sigma protocols, without relying on trusted setup. To obtain our second result, we devise a general framework via a new notion of statistical hash commitments that may be of independent interest.
Expand
Ruslan V. Skuratovskii, A. Р. Onufrieva, Aled Williams
ePrint Report ePrint Report
The goal of this investigation is effective method of key exchange which based on non-commutative group $G$. The results of Ko et al. \cite{kolee} is improved and generalized.

The size of a minimal generating set for the commutator subgroup of Sylow 2-subgroups of alternating group is found. The structure of the commutator subgroup of Sylow 2-subgroups of the alternating group ${A_{{2^{k}}}}$ is investigated and used in key exchange protocol which based on non-commutative group.

We consider non-commutative generalization of CDH problem \cite{gu2013new, bohli2006towards} on base of metacyclic group of Miller-Moreno type (minimal non-abelian group). We show that conjugacy problem in this group is intractable. Effectivity of computation is provided due to using groups of residues by modulo $n$. The algorithm of generating (designing) common key in non-commutative group with 2 mutually commuting subgroups is constructed by us.
Expand
Sam Kim
ePrint Report ePrint Report
Pseudorandom functions (PRFs) are fundamental objects in cryptography that play a central role in symmetric-key cryptography. Although PRFs can be constructed from one-way functions generically, these black-box constructions are usually inefficient and require deep circuits to evaluate compared to direct PRF constructions that rely on specific algebraic assumptions. From lattices, one can directly construct PRFs from the Learning with Errors (LWE) assumption (or its ring variant) using the result of Banerjee, Peikert, and Rosen (Eurocrypt 2012) and its subsequent works. However, all existing PRFs in this line of work rely on the hardness of the LWE problem where the associated modulus is super-polynomial in the security parameter.

In this work, we provide two new PRF constructions from the LWE problem that each focuses on either minimizing the depth of its evaluation circuit or providing key-homomorphism while relying on the hardness of the LWE problem with either a polynomial modulus or nearly polynomial modulus. Along the way, we introduce a new variant of the LWE problem called the Learning with Rounding and Errors (LWRE) problem. We show that for certain settings of parameters, the LWRE problem is as hard as the LWE problem. We then show that the hardness of the LWRE problem naturally induces a pseudorandom synthesizer that can be used to construct a low-depth PRF. The techniques that we introduce to study the LWRE problem can then be used to derive variants of existing key-homomorphic PRFs whose security can be reduced from the hardness of the LWE problem with a much smaller modulus.
Expand
Aizuwakamatsu, Japan, 3 October - 5 October 2020
Event Calendar Event Calendar
Event date: 3 October to 5 October 2020
Submission deadline: 1 May 2020
Notification: 1 August 2020
Expand
University of Twente, The Netherlands
Job Posting Job Posting

The Services and Cybersecurity (SCS) group at the University of Twente invites applications for a 4-year PhD position in secure data management.

In this PhD project, we will investigate cryptographic concepts for secure data management with a particular focus on searchable encryption schemes that enable the secure search over encrypted data. Existing searchable encryption schemes typically allow for some leakage in order to achieve efficient solutions, which makes them susceptible to leakage-abuse attacks. The PhD project will investigate different ways to attack such schemes and will deliver new schemes that are secure against such attacks while still being efficient. The developed solutions will be validated in the application domain of healthcare in collaboration with our partners CZ (a major Dutch health insurance company) and TNO (the Dutch Organization for Applied Scientific Research).

For more information and the link to apply, please visit:
https://www.utwente.nl/en/organization/careers/!/1097017/full-time-phd-position-in-secure-data-management

Closing date for applications:

Contact: Andreas Peter; a.peter@utwente.nl

More information: https://www.utwente.nl/en/organization/careers/!/1097017/full-time-phd-position-in-secure-data-management

Expand
Bertram Poettering, Paul Rösler
ePrint Report ePrint Report
The Authenticated Encryption with Associated Data (AEAD) primitive, which integrates confidentiality and integrity services under a single roof, found wide-spread adoption in industry and became indispensable in practical protocol design. Recognizing this, academic research put forward a large number of candidate constructions, many of which come with provable security guarantees. Nevertheless, the recent past has shaken up with the discovery of vulnerabilities, some of them fatal, in well-regarded schemes, stemming from weak underlying primitives, flawed security arguments, implementation-level vulnerabilities, and so on. Simply reacting to such findings by replacing broken candidates by better(?) ones is in many cases unduly, costly, and sometimes just impossible. On the other hand, as attack techniques and opportunities change over time, it seems venturous to propose any specific scheme if the intended lifetime of its application is, say, twenty years.

In this work we study a workable approach towards increasing the resilience against unforeseen breaks of AEAD primitives. Precisely, we consider the ability to combine two AEAD schemes into one such that the resulting AEAD scheme is secure as long as at least one of its components is (or: as long as at most one component is broken). We propose a series of such combiners, some of which work with fully generic AEAD components while others assume specific internal structures of the latter (like an encrypt-then-MAC design). We complement our results by proving the optimality of our constructions by showing the impossibility of combiners that get along with less invocations of the component algorithms.
Expand

21 February 2020

Hasso-Plattner-Institute, University of Potsdam, Germany
Job Posting Job Posting

The Cybersecurity - Identity Management group at the Hasso-Plattner-Institute (HPI), University of Potsdam is seeking to fill several PhD and PostDoc positions in the area of cryptography and privacy.

Your future tasks
  • Development of provably secure cryptographic protocols for real-world problems. Topics of interest include (but are not limited to):
    • Distributed identity management
    • Privacy-enhancing technologies
    • Foundations and solutions for real-world cryptography
  • Publish and present results at top-tier international conferences
  • Participate in teaching activities
Your skills
  • Master's degree (or PhD for postdoctoral position) in Computer Science, Mathematics, or a related area by the time of appointment
  • Profound knowledge in the areas of cryptography and IT security (for postdoctoral candidates proven in the form of publications in these areas)
  • Excellent English language skills
What we offer
  • Collaborative work environment in a newly established research group
  • Outstanding setting to conduct top academic research with strong connections to industry
  • Working at the HPI campus in Potsdam-Babelsberg (S-Bahn station Griebnitzsee) near to Berlin

We look forward to your application including two references, motivation letter and copies of relevant diplomas and certificates. Please submit your application documents (only as PDF) via email.

Closing date for applications:

Contact: Anja Lehman, email: anja.lehmann (at) hpi.de

More information: https://hpi.de/lehmann/

Expand
◄ Previous Next ►