International Association
for Cryptologic Research

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.

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.

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.

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.

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.

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.

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.

Event date: 3 October to 5 October 2020
Submission deadline: 1 May 2020
Notification: 1 August 2020

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

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.

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/

The cryptographic protocols mainly comprise functionalities such as public-key encryption, digital signatures, and key exchange. These cryptographic protocols are based on the difficulty of certain mathematical operations, such as finding the prime factors of a very large integer. However, recent advances in quantum computing mean that these difficult math problems might soon be solved efficiently, with a potentially serious impact upon our security. Realizing the availability of quantum computers from research labs to general purpose use in the near future, the preparation against such a threat has taken shape recently, and happening to be a fast growing topic of research referred as post-quantum cryptography (PQC). Nowadays, certain candidate families of post-quantum schemes have been realized including code-based, hash-based, multivariate, lattice-based and supersingular isogeny-based. Security of all these primitives are based on different mathematical problems which are believed to be hard even with respect to quantum computation and quantum communications. In this project, we aim to achieve the following goals: • To study the existing PQC schemes and demonstrate state of the art PQC following an extensive review. • To propose post-quantum schemes taking in account their possible application to IoT security or Blockchain.

Closing date for applications:

Contact: joaquin.garcia_alfaro@telecom-sudparis.eu and Kalpana.SINGH@irt-systemx.fr

Constraint Programming for Cryptanalysis of Symmetric Encryption Schemes

• Location: LIMOS, Clermont-Ferrand, France
• Salary: 2000€
• Duration: 1 year
• Keywords: Cryptanalysis symmetric, constraint programming, SAT solving, ILP.
• Starting date: As soon as possible, when we have a good candidate; at least before October 2020.

Your Profile

• A PhD in Computer Science, Applied Mathematics, Cryptography or related field.
• Competitive research record in symmetric cryptography or in constraint programming.
• Commitment, team working and a critical mind.
• Good written and verbal communication skills in English are essential.

This post-doc is founded by the ANR project Decrypt started in January 2019.

Transforming a theoretical cryptanalysis into a SAT problem or into a set of linear constraints could be a hard and time-consuming task. Our aim is to use constraint programming (CP) to simplify the way the symmetric key attacks are modeled and thus to overpass existing cryptanalytic results. Preliminary studies are really encouraging.

Goal

The main goal is to identify schemes and attacks for which it is possible to use off-the-shelf CP, SAT or ILP approaches. To achieve this goal, the work will be divided into the following tasks.

1. Study symmetric encryption schemes and identify for several schemes the different components that are used in the scheme design.
2. Design CP, SAT, and ILP models for cryptanalytic problems on selected schemes. We will mainly focus on the following attacks: cube attacks, conditional cube attacks with division property, (related-key) differential and linear cryptanalysis, word-based division property / integral distinguisher.
3. Experimentally evaluate CP, SAT, and ILP solvers on the models designed in previous tasks, and compare these solvers with existing dedicated cryptanalysis approaches. Design of a tool to automate this task is one of the goals of the project.

Closing date for applications:

Contact: Pascal Lafourcade pascal.Lafourcade@uca.fr

More information: https://decrypt.limos.fr/post/postdoc-offer-limos/

A Ph.D. position is open in université Jean Monnet. This Ph.D project aims to develop novel techniques that can protect cryptographic implementations against side-channel attacks and fault attacks. The protection studied will be mainly algorithmic protection, with experimental evaluation of their effectiveness and efficiency. Various directions can be explored with respect to the candidate background.

Closing date for applications:

Contact: Vincent Grosso

PQSecure Technologies, LLC is a growing startup company active in the area of post-quantum cryptographic engineering with focus on embedded and IoT devices. PQSecure is currently funded by National Science Foundation SBIR Phase II fund and is an active participant of National Institute of Standards and technology (NIST) for post-quantum cryptography. We are looking for a postdoc/research scientist with post-quantum cryptography and implementations experience and relevant publication records. Candidates should hold a PhD in Computer science/engineering, or electrical engineering, or applied mathematics with excellent programming skills and cryptographic protocol design. PQSecure offers a competitive hiring package including, 401k, health insurance, stock option, 3 weeks of PTO, travel reimbursement for relevant conferences, and etc.). The position is for one year with possibility of renewal based on the performance of the candidate. The salary will be $87,000 per year. PQSecure is located in the beautiful city Boca Raton, FL. The deadline for applications is February 15, 2020. The position will be open until filled.

Closing date for applications:

Contact: Dr. Reza Azarderakhsh razarder[a/t]pqsecurity.com

At Eurocrypt'19, Attrapadung presented several transformations that dynamically compose a set of attribute-based encryption (ABE) schemes for simpler predicates into a new ABE scheme for more expressive predicates. Due to the powerful unbounded and modular nature of his compositions, many new ABE schemes can be obtained in a systematic manner (including those that resolved some open problems at the time). However, his approach heavily relies on so-called q-type assumptions, which are not standard. Devising such powerful compositions from standard assumptions was left as an important open problem. In this paper, we present a new framework for constructing ABE schemes that allow unbounded and dynamic predicate compositions among them, and show that the adaptive security of these composed ABE will be preserved by relying only on the standard matrix Diffie-Hellman (MDDH) assumption. This thus resolves the open problem posed by Attrapadung. Our framework significantly expands an area of ABEs that are realizable from standard assumptions. This includes the following adaptively secure large-universe ABEs for Boolean formulae under MDDH. -- The first completely unbounded monotone key-policy (KP)/ciphertext-policy (CP) ABE. Previously, such ABE has been only recently proposed, but only for the KP and small-universe flavor (Kowalczyk and Wee, Eurocrypt'19). -- The first completely unbounded non-monotone KP/CP-ABE. Especially, our ABEs support a new type of non-monotonicity that subsumes previous two types of non-monotonicity, namely, by Ostrovsky et al. (CCS'07) and by Okamoto and Takashima (CRYPTO'10). -- The first non-monotone KP and CP-ABE with constant-size ciphertexts and secret keys, respectively. -- The first monotone KP and CP-ABE with constant-size secret keys and ciphertexts, respectively.

In ASIACRYPT 2019, Genise et al. describe GGH+19 a new somewhat homomorphic encryption scheme. The security relies on an inhomogeneous and non-structured variant of the NTRU assumption that they call MiNTRU. To allow for meaningful homomorphic computations, they use overstretched parameters, but they do not provide an analysis of their new assumption against the state-of-the-art attack of Kirchner and Fouque KF17 for overstretched modulus. We show that the parameters of GGH+19 do not satisfy the desired security by actually conducting the known analysis. We also report a successful break of the smallest set of parameters in around 15 hours of computations while they are claimed to reach 100 bits of security.

We consider a \emph{collision search problem} (CSP), where given a parameter $C$, the goal is to find $C$ collision pairs in a random function $f:[N] \rightarrow [N]$ (where $[N] = \{0,1,\ldots,N-1\})$ using $S$ bits of memory. Algorithms for CSP have numerous cryptanalytic applications such as space-efficient attacks on double and triple encryption. The best known algorithm for CSP is \emph{parallel collision search} (PCS) published by van Oorschot and Wiener, which achieves the time-space tradeoff $T^2 \cdot S = \tilde{O}(C^2 \cdot N)$.

In this paper, we prove that any algorithm for CSP satisfies $T^2 \cdot S = \tilde{\Omega}(C^2 \cdot N)$, hence the best known time-space tradeoff is optimal (up to poly-logarithmic factors in $N$). On the other hand, we give strong evidence that proving similar unconditional time-space tradeoff lower bounds on CSP applications (such as breaking double and triple encryption) may be very difficult, and would imply a breakthrough in complexity theory. Hence, we propose a new restricted model of computation and prove that under this model, the best known time-space tradeoff attack on double encryption is optimal.

Boneh, Waters and Zhandry (CRYPTO 2014) used multilinear maps to provide a solution to the long-standing problem of public-key broadcast encryption (BE) where all parameters in the system are small. In this work, we improve their result by providing a solution that uses only bilinear maps and Learning With Errors (LWE). Our scheme is fully collusion-resistant against any number of colluders, and can be generalized to an identity-based broadcast system with short parameters. Thus, we reclaim the problem of optimal broadcast encryption from the land of “Obfustopia”.

Our main technical contribution is a ciphertext policy attribute based encryption (CP-ABE) scheme which achieves special efficiency properties – its ciphertext size, secret key size, and public key size are all independent of the size of the circuits supported by the scheme. We show that this special CP-ABE scheme implies BE with optimal parameters; but it may also be of independent interest. Our constructions rely on a novel interplay of bilinear maps and LWE, and are proven secure in the generic group model.

Let $k \ge 2$ be an integer, define $$ S_t^k:=\Bigg\{(a,b)\in \mathbb{Z}^2\ \Big| \ { 0 \le a,b \le 2^{k}-2,\ a+b\equiv t ~(\text{mod} \ 2^k-1),\ \w(a)+\w(b)\le{k-1}}\Bigg\},$$ where $t \in \mathbb{Z}, 1 \le t \le 2^k-2$. This paper gives the upper bound of cardinality of $S_t^k$ when $\w(t)\le 10$, proving that a conjecture proposed by Tu and Deng in the case.