International Association
for Cryptologic Research

Job description. We are looking for a PhD student to join our team as a research intern (during the summer). The internship will take place in the Concrete-Framework team and will mix some research — discovering new cryptographic techniques to compute on encrypted data — and some implementation — working with the developers to implement the research results into Concrete, the open-source cryptographic library in Rust our team is writing and maintaining (https://github.com/zama-ai/concrete). The goal of this internship will be to understand homomorphic encryption, improve the existing techniques and implement the results in Concrete. In particular, for the latter, your main tasks will be to write high performance code in Rust or improve the existing Rust code to make it faster.
We believe this experience will train the candidate both on the research and the implementation side, since he/she/they will work with a team of cryptographers and will implement the results in an open source library that is used by the community.

Preferred experience. He / She / They should:

• already be a PhD student,
• have a solid background in cryptography, possibly with some knowledge in FHE,
• have some development experience, possibly with a background in Rust,
• be passionate about privacy, open source and willing to learn,
• have a problem-solving attitude,
• have good communication skills.

Full remote is possible.

Closing date for applications:

Contact: To know more about the job offer and to apply, visit https://www.welcometothejungle.com/en/companies/zama/jobs/intern-research-and-concrete-lib-summer_paris?q=62533b0c4028334941d506e9b41b0004&o=918987&e=companies_jobs

More information: https://www.welcometothejungle.com/en/companies/zama/jobs/intern-research-and-concrete-lib-summer_paris?q=62533b0c4028334941d506e9b41b0004&o=918987&e=companies_jobs

Job description. The candidate and his/her/their team will be responsible for:

• discovering new cryptographic techniques to compute on encrypted data,
• working with the engineering and product teams to implement his/her/their research into our products,
• design robust tests and benchmarks to validate his/her/their research and its implementation,
• review the latest published research, and inform the team on potential new applications,
• work with the entire team to define the research and product roadmaps,
• publishing papers, filing patents and presenting his/her/their work at academic conferences.

The team. The Concrete Framework division is writing and maintaining several open-source cryptographic libraries and tools dedicated to Fully Homomorphic Encryption (FHE). Those libraries and tools are written with different languages (rust for libraries, cpp for the compiler, python for frontend, etc…) and is targeting several environment (linux/macos/…) and/or hardware (cpu/gpu/…). As example one of those libraries, Concrete-core is used as the backbone of the whole framework. It implements various cryptographic primitives. The codebase uses the Rust programming language as its main language, but it is expected to host hardware-specific code written in other languages in the near future.

Preferred experience. We are looking for different experience profiles for this position, from young researchers (right after the end of the PhD) to more senior ones. He/she/they should:

• have a PhD in cryptography or equivalent,
• have deep knowledge of homomorphic encryption,
• have (optionally) knowledge of LWE hardness and security,
• have (optionally) knowledge of machine learning,
• be passionate about privacy and open source software,
• have good written and oral communication skills.

Full remote is possible, with a willingness to come to Paris quarterly.

Closing date for applications:

Contact: To know more about the job offer and to apply, visit https://www.welcometothejungle.com/en/companies/zama/jobs/senior-researcher-cryptography_paris?q=62533b0c4028334941d506e9b41b0004&o=341359&e=companies_jobs

More information: https://www.welcometothejungle.com/en/companies/zama/jobs/senior-researcher-cryptography_paris?q=62533b0c4028334941d506e9b41b0004&o=341359&e=companies_jobs

The Insight SFI Research Centre for Data Analytics invites applications for a Post-Doctoral Researcher position in the area of Security/Privacy and Data Analytics. The successful candidate will work under the supervision of Dr Paolo Palmieri, Lecturer in Cyber Security, and Prof. Barry O’Sullivan, Professor of Computer Science, in the School of Computer Science & Information Technology, University College Cork, Ireland.

The Post-Doctoral Researcher will work primarily on an industry project with a leading industry partner in the area of privacy and security. The position is initially for an 18-month fixed-term period, and may subsequently lead to other research opportunities with industry/academic partners. Funding for conferences and equipment is available as part of the project.

The ideal applicant holds a PhD in Computer Science or related disciplines and has experience in cyber security and privacy research. He/She has a good track record in relevant conferences and journals and has research experience in one or more of the following research areas: differential privacy, anonymity, re-identification, secure composition and/or cryptography. Previous experience in working with industry partners is an asset.

This position is part of the Science Foundation Ireland newly launched Empower Spoke which is a new €10 million academic and industry research programme, designed to future proof EU data flows and drive innovations in data protection internationally.

Closing date for applications:

Contact: Informal inquiries can be made in confidence to Dr. Paolo Palmieri, at: p.palmieri@cs.ucc.ie

Applications should be submitted through the University portal at https://ore.ucc.ie/ (search for reference number: 054451)

Deadline: March 18, 2022 at 12:00 (noon) Irish time.

More information: http://security.ucc.ie/vacancies.html

First of all we take a thorough look at an error in a paper by Daemen et al. (ToSC 2018) which looks at minimal requirements for tree-based hashing based on multiple primitives, including block ciphers. This reveals that the error is more fundamental than previously shown by Gunsing et al. (ToSC 2020), which is mainly interested in its effect on the security bounds. It turns out that the cause for the error is due to an essential oversight in the interaction between the different oracles used in the indifferentiability proofs. As a matter of fact, this error appeared in multiple earlier indifferentiability papers, including the optimal indifferentiability of the sum of permutations (EUROCRYPT 2018) and the recent ABR+ construction (EUROCRYPT 2021). We discuss in detail how this oversight is caused and how it can be avoided.

We next demonstrate how the negative effects on the security bound of the construction by Daemen et al. can be resolved. Instead of only allowing a truncated output, we generalize the construction to allow for any finalization function and investigate the security of this for five different types of finalization. Our findings, among others, show that the security of the SHA-2 mode does not degrade if the feed-forward is dropped and that the modern BLAKE3 construction is secure in principle but that its use of the extendable output requires its counter used for random access to be public. Finally, we introduce the tree sponge, a generalization of the sequential sponge construction with parallel absorbing and squeezing.

Homomorphic encryption (HE) protects data in-use, but can be computationally expensive. To avoid the costly bootstrapping procedure that refreshes ciphertexts, some works have explored client-aided outsourcing protocols, where the client intermittently refreshes ciphertexts for a server that is performing homomorphic computations. But is this approach secure against malicious servers?

We present a CPA-secure encryption scheme that is completely insecure in this setting. We define a new notion of security, called funcCPA, that we prove is sufficient. Additionally, we show:

- Homomorphic encryption schemes that have a certain type of circuit privacy -- for example, schemes in which ciphertexts can be ``sanitized''-- are funcCPA-secure.

- In particular, assuming certain existing HE schemes are CPA-secure, they are also funcCPA-secure.

- For certain encryption schemes, like Brakerski-Vaikuntanathan, that have a property that we call oblivious secret key extraction, funcCPA-security implies circular security -- i.e., that it is secure to provide an encryption of the secret key in a form usable for bootstrapping (to construct fully homomorphic encryption).

In summary, funcCPA-security lies strictly between CPA-security and CCA2-security (under reasonable assumptions), and has an interesting relationship with circular security, though it is not known to be equivalent.

\textit{Interactive Oracle Proofs} (IOPs) are a new type of proof-system that combines key properties of interactive proofs and PCPs: IOPs enable a verifier to be convinced of the correctness of a statement by interacting with an untrusted prover while reading just a few bits of the messages sent by the prover. IOPs have become very prominent in the design of efficient proof-systems in recent years. In this work we study \textit{succinct IOPs}, which are IOPs in which the communication complexity is polynomial (or even linear) in the original witness. While there are strong impossibility results for the existence of succinct PCPs (i.e., PCPs whose length is polynomial in the witness), it is known that the rich class of NP relations that are decidable in small space have succinct IOPs. In this work we show both new applications, and limitations, for succinct IOPs: \begin{itemize} \item First, using one-way functions, we show how to compile IOPs into zero-knowledge \textit{proofs}, while nearly preserving the proof length. This complements a recent line of work, initiated by Ben~Sasson~\etal{}~(TCC, 2016B), who compile IOPs into super-succinct zero-knowledge \textit{arguments}. Applying the compiler to the state-of-the-art succinct IOPs yields zero-knowledge proofs for bounded-space NP relations, with communication that is nearly equal to the original witness length. This yields the shortest known zero-knowledge proofs from the minimal assumption of one-way functions.

\item Second, we give a barrier for obtaining succinct IOPs for more general NP relations. In particular, we show that if a language has a succinct IOP, then it can be decided in \textit{space} that is proportionate only to the witness length, after a bounded-time probabilistic preprocessing. We use this result to show that under a simple and plausible (but to the best of our knowledge, new) complexity-theoretic conjecture, there is no succinct IOP for CSAT. \end{itemize}

Homomorphic encryption (HE) is being widely used for privacy-preserving computation. Since HE schemes only support polynomial operations, it is prevalent to use polynomial approximations of non-polynomial functions. We cannot monitor the intermediate values during the evaluation; as a consequence, we should utilize polynomial approximations with sufficiently large approximation intervals to prevent the failure of the evaluation. However, the large approximation interval potentially accompanies computational overhead, and it is a serious bottleneck of HE application on real data.

In this work, we introduce domain extension polynomials (DEPs) that extend the domain interval of functions by a factor of $k$ while preserving the feature of the original function on its original domain interval. By repeatedly iterating the domain-extension process with DEPs, we can extend with $O(\log{K})$ multiplications the domain of given function by a factor of $K$ while the feature of the original function is preserved on its original domain interval.

By using DEPs, we can efficiently evaluate in encrypted state a function that converges at infinities. To uniformly approximate the function on $[-R,R]$, our method exploits $O(\log{R})$ multiplications and $O(1)$ memory. This is more efficient than the current best approach, the minimax approximation and Paterson-Stockmeyer algorithm, which uses $O(\sqrt{R})$ multiplications and $O(\sqrt{R})$ memory for the evaluation. As another application of DEPs, we also suggest a method to manage the risky outliers from a wide interval $[-R,R]$ by using $O(\log{R})$ additional multiplications.

As a real-world application, we exploit our uniform approximation of the logistic function on wide intervals to logistic regression. We trained the model on large public datasets in encrypted state using the polynomial approximation of the logistic function on $[-7683,7683]$.

In this paper, we investigate permutation rotation-symmetric (shift-invariant) vectorial Boolean functions on $n$ bits that are liftings from Boolean functions on $k$ bits, for $k\leq n$. These functions generalize the well-known map used in the current Keccak hash function, which is generated via the Boolean function $x_1+x_1x_2+x_3$. We provide some general constructions, and also study the affine equivalence between rotation-symmetric Sboxes and describe the corresponding relationship between the Boolean function they are associated with. In the process, we point out some inaccuracies in the existing literature.

A distribution is k-incompressible, Yao [FOCS ’82], if no efficient compression scheme compresses it to less than k bits. While being a natural measure, its relation to other computational analogs of entropy such as pseudoentropy, Hastad, Impagliazzo, Levin, and Luby [SICOMP 99], and to other cryptographic hardness assumptions, was unclear.

We advance towards a better understating of this notion, showing that a k-incompressible distribution has (k−2) bits of next-block pseudoentropy, a refinement of pseudoentropy introduced by Haitner, Reingold, and Vadhan [SICOMP ’13]. We deduce that a samplable distribution X that is (H(X) + 2)-incompressible, implies the existence of one-way functions.

In this report we investigate how to generate secure elliptic curves over sextic extension of prime fields of size roughly 64 bits to achieve 128-bit security. In particular, we present one of such curves over a 64-bit prime field, which we named Cheetah, and provide its security parameter. This curve is particularly well-suited for zero-knowledge applications such as FRI-based STARK proving systems, as its base prime field has the property of having a large two-adicity, necessary for FFT-related operations and at the same time it is used for elliptic curve-based signatures. We also provide a prototype implementation of this curve in Rust, featuring constant-time arithmetic and no use of the Rust standard library for WebAssembly support.

In this paper, we analyze the hardness of the Matrix Code Equivalence (MCE) problem for matrix codes endowed with the rank metric, and provide the first algorithms for solving it. We do this by making a connection to another well-known equivalence problem from multivariate cryptography - the Isomorphism of Polynomials (IP). We show that MCE is equivalent to the homogeneous version of the Quadratic Maps Linear Equivalence (QMLE) problem. Using the same birthday techniques known for IP, we present an algorithm for MCE running in time $\mathcal{O}^*( q^{\frac{2}{3}(n+m)})$, and an algorithm for MCE with roots, running in time $\mathcal{O}^*(q^{m})$. We verify these algorithms in practice.

A seminal 2013 paper by Lyubashevsky, Peikert, and Regev proposed basing post-quantum cryptography on ideal lattices and supported this proposal by giving a polynomial-time security reduction from the approximate Shortest Independent Vectors Problem (SIVP) to the Decision Learning With Errors (DLWE) problem in ideal lattices. We give a concrete analysis of this multi-step reduction. We find that the tightness gap in the reduction is so great as to vitiate any meaningful security guarantee, and we find reasons to doubt the feasibility in the foreseeable future of the quantum part of the reduction. In addition, when we make the reduction concrete it appears that the approximation factor in the SIVP problem is far larger than expected, a circumstance that causes the corresponding approximate-SIVP problem most likely not to be hard for proposed cryptosystem parameters.

We present here the design and implementation of ecGFp5, an elliptic curve meant for a specific compute model in which operations modulo a given 64-bit prime are especially efficient. This model is primarily intended for running operations in a virtual machine that produces and verifies zero-knowledge STARK proofs. We describe here the choice of a secure curve, amenable to safe cryptographic operations such as digital signatures, that maps to such models, while still providing reasonable performance on general purpose computers.

Homomorphic encryption (HE) is a promising technology for protecting data in use, with considerable recent years progress towards attaining practical runtime performance. However the high storage overhead associated with HE remains an obstacle preventing its large scale adoption. In this work we propose a new storage solution in the two-server model resolving the high storage overhead associated with HE, while preserving data confidentiality. Our solution attains the following desired properties:

1) *Compact storage* with zero overhead over storing AES ciphertexts, and $10\times$ to $10,000\times$ better than storing CKKS ciphertexts.

2) *Fast runtime performance* for storage and retrieval, only twice the time of directly storing and retrieving HE ciphertexts.

3) *Dynamic control during retrieval* of the HE parameters and the data items to be packed in each HE ciphertext.

4) *Plug-and-play compatibility* with any homomorphic computation.

We implemented our solution into a proof-of-concept system running on AWS EC2 instances with AWS S3 storage, empirically demonstrating its appealing performance. As a central tool we introduce the first perfect secret sharing scheme with fast homomorphic reconstruction over the reals; this may be of independent interest.

An aggregate signature (ASIG) scheme allows any user to compress multiple signatures into a short signature called an aggregate signature. While a conventional ASIG scheme cannot detect any invalid messages from an aggregate signature, an ASIG scheme with detecting functionality (D-ASIG) has an additional property which can identify invalid messages from aggregate signatures. Hence, D-ASIG is useful to reduce the total amount of signature-sizes on a channel. On the other hand, development of quantum computers has been advanced recently. However, all existing D-ASIG schemes are insecure against attacks using quantum algorithms, which we call quantum attacks. In this paper, we propose a D-ASIG scheme with quantum-security which means security in a quantum setting. Hence, we first introduce quantum-security notions of ASIGs and D-ASIGs because there is no research on such security notions for (D-)ASIGs. Second, we propose a lattice-based aggregate one-time signature scheme with detecting functionality, and prove that this scheme satisfies our quantum-security in the quantum random oracle model and the certified key model. Hence, this scheme is the first quantum-secure D-ASIG.

We address Partial Key Exposure attacks on CRT-RSA on secret exponents $d_p, d_q$ with small public exponent $e$. For constant $e$ it is known that the knowledge of half of the bits of one of $d_p, d_q$ suffices to factor the RSA modulus $N$ by Coppersmith's famous {\em factoring with a hint} result. We extend this setting to non-constant $e$. Somewhat surprisingly, our attack shows that RSA with $e$ of size $N^{\frac 1 {12}}$ is most vulnerable to Partial Key Exposure, since in this case only a third of the bits of both $d_p, d_q$ suffices to factor $N$ in polynomial time, knowing either most significant bits (MSB) or least significant bits (LSB).

Let $ed_p = 1 + k(p-1)$ and $ed_q = 1 + \ell(q-1)$. On the technical side, we find the factorization of $N$ in a novel two-step approach. In a first step we recover $k$ and $\ell$ in polynomial time, in the MSB case completely elementary and in the LSB case using Coppersmith's lattice-based method. We then obtain the prime factorization of $N$ by computing the root of a univariate polynomial modulo $kp$ for our known $k$. This can be seen as an extension of Howgrave-Graham's {\em approximate divisor} algorithm to the case of {\em approximate divisor multiples} for some known multiple $k$ of an unknown divisor $p$ of $N$. The point of {\em approximate divisor multiples} is that the unknown that is recoverable in polynomial time grows linearly with the size of the multiple $k$.

Our resulting Partial Key Exposure attack with known MSBs is completely rigorous, whereas in the LSB case we rely on a standard Coppersmith-type heuristic. We experimentally verify our heuristic, thereby showing that in practice we reach our asymptotic bounds already using small lattice dimensions. Thus, our attack is highly efficient.

Commit-and-open Sigma-protocols are a popular class of protocols for constructing non-interactive zero-knowledge arguments and digital-signature schemes via the Fiat-Shamir transformation. Instantiated with hash-based commitments, the resulting non-interactive schemes enjoy tight online-extractability in the random oracle model. Online extractability improves the tightness of security proofs for the resulting digital-signature schemes by avoiding lossy rewinding or forking-lemma based extraction. In this work, we prove tight online extractability in the quantum random oracle model (QROM), showing that the construction supports post-quantum security. First, we consider the default case where committing is done by element-wise hashing. In a second part, we extend our result to Merkle-tree based commitments. Our results yield a significant improvement of the provable post-quantum security of the digital-signature scheme Picnic. Our analysis makes use of a recent framework by Chung et al. for analysing quantum algorithms in the QROM using purely classical reasoning. Therefore, our results can to a large extent be understood and verified without prior knowledge of quantum information science.

It is a long standing open problem to find search to decision reductions for structured versions of the decoding problem of linear codes. Such results in the lattice-based setting have been carried out using number fields: Polynomial–LWE, Ring–LWE, Module–LWE and so on. We propose a function field version of the LWE problem. This new framework leads to another point of view on structured codes, e.g. quasi-cyclic codes, strengthening the connection between lattice-based and code-based cryptography. In particular, we obtain the first search to decision reduction for structured codes. Following the historical constructions in lattice–based cryptography, we instantiate our construction with function fields analogues of cyclotomic fields, namely Carlitz extensions, leading to search to decision reductions on various versions of Ring-LPN, which have applications to secure multi party computation and to an authentication protocol.

This paper provides efficient authenticated-encryption (AE) schemes in which a ciphertext is a commitment to the key. These are extended, at minimal additional cost, to schemes where the ciphertext is a commitment to all encryption inputs, meaning key, nonce, associated data and message. Our primary schemes are modifications of GCM (for basic, unique-nonce AE security) and AES-GCM-SIV (for misuse-resistant AE security) and add both forms of commitment without any increase in ciphertext size. We also give more generic, but somewhat more costly, solutions.

In this paper, we propose a practical signature scheme based on the alternating trilinear form equivalence problem. Our scheme is inspired by the Goldreich-Micali-Wigderson's zero-knowledge protocol for graph isomorphism, and can be served as an alternative candidate for the NIST's post-quantum digital signatures. First, we present theoretical evidences to support its security, especially in the post-quantum cryptography context. The evidences are drawn from several research lines, including hidden subgroup problems, multivariate cryptography, cryptography based on group actions, the quantum random oracle model, and recent advances on isomorphism problems for algebraic structures in algorithms and complexity. Second, we demonstrate its potential for practical uses. Based on algorithm studies, we propose concrete parameter choices, and then implement a prototype. One concrete scheme achieves 128 bit security with public key size ~ 4100 bytes, signature size ~ 6800 bytes, and running times (key generation, sign, verify) ~ 0.8ms on a common laptop computer.