International Association
for Cryptologic Research

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.

In this paper, a multivariate polynomial and exponential mappings based password protocol is presented. The method can be utilized in public domains. The key generator generates a vector, intended to be used as a password by the authentication protocol subsequently, such that when the vector is substituted and evaluated in certain fixed multivariate polynomials -- that may be listed in a public domain -- the value $0$ is found as a result of proper authentication. The public domain in this context could be internal to a large, and possibly distributed, system. The key generator can take hints from the owner of the password to generate the particular zero vector to suit the user. It may take into consideration biometric and any other user specific information at the time of key generation. The information collected by the key generator can be saved by the owner of the password for its possible retrieval upon requisition by the user, during the period of its validity, in case it is forgotten by the user.

Despite the fundamental importance of delay functions, underlying both the classic notion of a time-lock puzzle and the more recent notion of a verifiable delay function, the only known delay function that offers both sufficient structure for realizing these two notions and a realistic level of practicality is the ``iterated squaring'' construction of Rivest, Shamir and Wagner. This construction, however, is based on rather strong assumptions in groups of hidden orders, such as the RSA group (which requires a trusted setup) or the class group of an imaginary quadratic number field (which is still somewhat insufficiently explored from the cryptographic perspective). For more than two decades, the challenge of constructing delay functions in groups of known orders, admitting a variety of well-studied instantiations, has eluded the cryptography community.

In this work we prove that there are no constructions of generic-group delay functions in cyclic groups of known orders: We show that for any delay function that does not exploit any particular property of the representation of the underlying group, there exists an attacker that completely breaks the function's sequentiality when given the group's order. As any time-lock puzzle and verifiable delay function give rise to a delay function, our result holds for these two notions we well, and explains the lack of success in resolving the above-mentioned long-standing challenge. Moreover, our result holds even if the underlying group is equipped with a $d$-linear map, for any constant $d \geq 2$ (and even for super-constant values of $d$ under certain conditions).

At the core of Apple's iMessage is a signcryption scheme that involves symmetric encryption of a message under a key that is derived from the message itself. This motivates us to formalize a primitive we call Encryption under Message-Derived Keys (EMDK). We prove security of the EMDK scheme underlying iMessage. We use this to prove security of the signcryption scheme itself, with respect to definitions of signcryption we give that enhance prior ones to cover issues peculiar to messaging protocols. Our provable-security results are quantitative, and we discuss the practical implications for iMessage.

A non-interactive zero-knowledge (NIZK) protocol enables a prover to convince a verifier of the truth of a statement without leaking any other information by sending a single message. The main focus of this work is on exploring short pairing-based NIZKs for all NP languages based on standard assumptions. In this regime, the seminal work of Groth, Ostrovsky, and Sahai (J.ACM'12) (GOS-NIZK) is still considered to be the state-of-the-art. Although fairly efficient, one drawback of GOS-NIZK is that the proof size is multiplicative in the circuit size computing the NP relation. That is, the proof size grows by $O(|C|\lambda)$, where $C$ is the circuit for the NP relation and $\lambda$ is the security parameter. By now, there have been numerous follow-up works focusing on shortening the proof size of pairing-based NIZKs, however, thus far, all works come at the cost of relying either on a non-standard knowledge-type assumption or a non-static $q$-type assumption. Specifically, improving the proof size of the original GOS-NIZK under the same standard assumption has remained as an open problem.

Our main result is a construction of a pairing-based NIZK for all of NP whose proof size is additive in $|C|$, that is, the proof size only grows by $|C| +\poly(\lambda)$, based on the decisional linear (DLIN) assumption. Since the DLIN assumption is the same assumption underlying GOS-NIZK, our NIZK is a strict improvement on their proof size.

As by-products of our main result, we also obtain the following two results: (1) We construct a perfectly zero-knowledge NIZK (NIPZK) for NP relations computable in NC1 with proof size $|w| \cdot \poly(\lambda)$ where $|w|$ is the witness length based on the DLIN assumption. This is the first pairing-based NIPZK for a non-trivial class of NP languages whose proof size is independent of $|C|$ based on a standard assumption. (2)~We construct a universally composable (UC) NIZK for NP relations computable in NC1 in the erasure-free adaptive setting whose proof size is $|w| \cdot \poly(\lambda)$ from the DLIN assumption. This is an improvement over the recent result of Katsumata, Nishimaki, Yamada, and Yamakawa (CRYPTO'19), which gave a similar result based on a non-static $q$-type assumption.

The main building block for all of our NIZKs is a constrained signature scheme with decomposable online-offline efficiency. This is a property which we newly introduce in this paper and construct from the DLIN assumption. We believe this construction is of an independent interest.

An updatable encryption scheme is a symmetric-key encryption scheme that supports key-rotation on ciphertexts. A server that hosts a user's encrypted data can use a user-provided update token to rotate the key under which the data is encrypted while not learning any information about the underlying data.

This work's contributions are threefold. First, we introduce new definitions for updatable encryption (in the ciphertext-dependent setting) that capture desirable security properties not covered in prior work. Next, we construct two new updatable encryption schemes. The first construction relies only on symmetric cryptographic primitives but only supports a bounded number of key rotations. The second supports a (nearly) unbounded number of updates and relies on almost key-homomorphic PRFs. We construct an efficient almost key-homomorphic PRF from the Ring Learning with Errors (RLWE) assumption to concretely instantiate our second construction. Finally, we implement both constructions and compare their performance to prior work. Our RLWE-based construction outperforms an existing updatable encryption scheme based on the hardness of DDH in elliptic-curve groups by over 200x in speed. Our construction based only on symmetric primitives has the highest encryption throughput, approaching the performance of AES, and the highest decryption throughput on ciphertexts that were re-encrypted fewer than fifty times, at which point the RLWE construction dominates.