International Association
for Cryptologic Research

In the threshold version of Paillier's encryption scheme a set of parties hold a share of the secret decryption key. Whenever a ciphertext is to be decrypted, the parties sends their decryption shares, which are then verified for correctness and combined into the plaintext. The scheme has been widely adopted in various applications, from secure voting to general purpose MPC protocols. However, among handful proposals for a maliciously secure scheme, one must choose between an efficient implementation that relies on non-standard assumptions or an infeasible one that relies on widely acceptable assumptions.

In this work, we present a new protocol that combines the benefits of both worlds. We depart from the efficient scheme, which was proven secure relying on non-standard assumptions, and for the first time, prove that it is secure under standard assumptions only. This is possible thanks to a novel reduction technique, from the soundness of a zero-knowledge proof of equality of discrete logs, to the factoring problem. Furthermore, our simple and efficient proof supports batching, and hence enables batched threshold Paillier decryption for the first time.

Until now, verifying that a decryption share is correct was the bottleneck of threshold Paillier schemes, and prevented its implementation in practice (unless one is willing to rely on a trusted dealer). Our new proof and batching techniques shift that bottleneck back to the plaintext reconstruction, just like in the semi-honest setting, and render threshold Paillier practical for the first time, supporting large scale deployments.

We implemented our scheme and report our evaluation with up to 1000 parties, in the dishonest majority setting. For instance, over an EC2 C6i machine, we get a throughput of about 50 and 3.6 decryptions per second, when run over a network of 100 and 1000 parties, respectively.

In this article, we discuss the decoding of Gabidulin and related codes from a cryptographic point of view, and we observe that these codes can be decoded solely from the knowledge of a generator matrix. We then extend and revisit Gibson and Overbeck attacks on the generalized GPT encryption scheme (instantiated with the Gabidulin code) for different ranks of the distortion matrix. We apply our attack to the case of an instantiation with twisted Gabidulin codes.

We present a new method for transforming zero-knowledge protocols in the designated verifier setting into public-coin protocols, which can be made non-interactive and publicly verifiable. Our transformation applies to a large class of ZK protocols based on oblivious transfer. In particular, we show that it can be applied to recent, fast protocols based on vector oblivious linear evaluation (VOLE), with a technique we call VOLE-in-the-head, upgrading these protocols to support public verifiability. Our resulting ZK protocols have linear proof size, and are simpler, smaller and faster than related approaches based on MPC-in-the-head.

To build VOLE-in-the-head while supporting both binary circuits and large finite fields, we develop several new technical tools. One of these is a new proof of security for the SoftSpokenOT protocol (Crypto 2022), which generalizes it to produce certain types of VOLE correlations over large fields. Secondly, we present a new ZK protocol that is tailored to take advantage of this form of VOLE, which leads to a publicly verifiable VOLE-in-the-head protocol with only 2x more communication than the best, designated-verifier VOLE-based protocols.

We analyze the soundness of our approach when made non-interactive using the Fiat-Shamir transform, using round-by-round soundness. As an application of the resulting NIZK, we present FAEST, a post-quantum signature scheme based on AES. FAEST is the first AES-based signature scheme to be smaller than SPHINCS+, with signature sizes between 5.6 and 6.6kB at the 128-bit security level. Compared with the smallest version of SPHINCS+ (7.9kB), FAEST verification is slower, but the signing times are between 8x and 40x faster.

Consider the problem of efficiently evaluating isogenies $\phi: \mathcal{E} \to \mathcal{E}/H$ of elliptic curves over a finite field $\mathbb{F}_q$, where the kernel \(H = \langle{G}\rangle\) is a cyclic group of odd (prime) order: given \(\mathcal{E}\), \(G\), and a point (or several points) $P$ on $\mathcal{E}$, we want to compute $\phi(P)$. This problem is at the heart of efficient implementations of group-action- and isogeny-based post-quantum cryptosystems such as CSIDH. Algorithms based on Vélu's formul\ae{} give an efficient solution to this problem when the kernel generator $G$ is defined over $\mathbb{F}_q$. However, for general isogenies, \(G\) is only defined over some extension $\mathbb{F}_{q^k}$, even though $\langle{G}\rangle$ as a whole (and thus \(\phi\)) is defined over the base field $\mathbb{F}_q$; and the performance of Vélu-style algorithms degrades rapidly as $k$ grows. In this article we revisit the isogeny-evaluation problem with a special focus on the case where $1 \le k \le 12$. We improve Vélu-style isogeny evaluation for many cases where \(k = 1\) using special addition chains, and combine this with the action of Galois to give greater improvements when \(k > 1\).

Code-Based Cryptosystem, CBC, is one of the candidates for Post-Quantum Cryptosystems, PQCs. Its security primarily bases on the Syndrome Decoding Problem, SDP. In this paper, we focus on the rank CBC whose security relies on the rank SDP. The GRS (Gaborit-Ruatta-Schrek) algorithm is well known as the current best decoding algorithm for the rank SDP. We propose the quantum version of the GRS algorithm. Then, we introduce the attack strategy using that quantum algorithm for previous rank CBCs remained at the 2nd Round of the NIST's PQC standardization project, and consider the quantum security for those cryptosystems. We present a result that is effective for RQC by our attack method, so give new RQC's instances which is secure against that attack.

We show that the key agreement scheme [Multim. Tools Appl. 80:799-829, 2021] is flawed. (1) The scheme is a hybrid which piles up various tools such as public key encryption, signature, symmetric key encryption, hash function, cancelable templates from thumb fingerprints, and elliptic curve cryptography. These tools are excessively used because key agreement is just a simple cryptographic primitive in contrast to public key encryption. (2) The involved reliance is very intricate. Especially, the requirement for a secure channel between two parties is generally unavailable.

We are looking for two motivated PhD students for projects in provable post-quantum security of e.g. the sponge construction and fiat shamir signatures. The envisioned projects will use quantum techniques to tackle post-quantum security questions. The positions are at the technical University of Denmark, where you will be part of a rapidly growing cryptography research environment.

Closing date for applications:

Contact: Christian Majenz (chmaj@dtu.dk)

More information: https://efzu.fa.em2.oraclecloud.com/hcmUI/CandidateExperience/da/sites/CX_1/requisitions/preview/1983/?lastSelectedFacet=LOCATIONS&selectedLocationsFacet=300000000228648

In the Faculty of Computer Science, Electrical Engineering and Mathematics, the Institute of Computer Science – Department "Codes and Cryptography" – within this scope, we invite applications for the following fixed-term position (100% of the regular working time), which will start at the earliest opportunity:

Research Assistant (f/m/d) (salary is according to E13 TV-L)

The position is embedded in the project “Photonic Quantum Computing (PhoQC)” of the “Ministerium für Kultur und Wissenschaft” of the state of Northrhine-Westfalia (MKW NRW).

It is a full-time qualification position to support a PhD-project. The initial contract is for three years but limited to the duration of the PhD-project. An extension to finish the PhD is possible in accordance with the rules of the WissZeitVG.

Your duties and responsibilites:

• Complexity theoretic analysis of Boson-Sampling-like experiments
• Development of quantum algorithms applying Boson Sampling to solve practical tasks
• Development and analysis of theoretical frameworks for universal quantum computing based on quantum photonics
• Teaching on the order of 4 teaching hours (SWS) per week

Hiring requirement:

• scientific Master degree in computer science, mathematics or physics

It is expected for the successful candidate to have an established academic profile and previous experience in at least one of the following areas:

• Quantum algorithms
• Quantum complexity theory
• Theoretical quantum photonics

Closing date for applications:

Contact: Please send your application including a CV using the Ref. No. 5979 to: bloemer@upb.de. Information regarding the processing of your person data can be located at: https://www.uni-paderborn.de/en/zv/personaldatenschutz.

More information: https://www.uni-paderborn.de/fileadmin/zv/4-4/stellenangebote/Kennziffer5979_-_Englisch.pdf

Non-Interactive Verifiable Secret Sharing (NI-VSS) is a technique for distributing a secret among a group of individuals in a verifiable manner, such that shareholders can verify the validity of their received share and only a specific number of them can access the secret. VSS is a fundamental tool in cryptography and distributed computing. In this paper, we present an efficient NI-VSS scheme using Zero-Knowledge (ZK) proofs on secret shared data. While prior VSS schemes have implicitly used ZK proofs on secret shared data, we specifically use their formal definition recently provided by Boneh et al. in CRYPTO 2019. Our proposed NI-VSS scheme uses a quantum random oracle and a quantum computationally hiding commitment scheme in a black-box manner, which ensures its ease of use, especially in post-quantum threshold protocols. The practicality of the proposed NI-VSS is confirmed by our implementation results, establishing it as a viable choice for large-scale threshold protocols. Using the proposed NI-VSS scheme, a dealer can share a secret with 4096 parties in less than 2 seconds, and the shareholders can verify the validity of their shares in less than 2 milliseconds. We demonstrate the potential of new NI-VSS scheme by revisiting several threshold protocols and improving their efficiency. Specifically, we present two DKG protocols for CSIDH-based primitives, that outperform the current state of the art. Furthermore, we show similar improvements in some threshold signatures built based on Schnorr and CSI-FiSh signature schemes. We think, due to its remarkable efficiency and ease of use, the new NI-VSS scheme can be a valuable tool for a wide range of threshold protocols.

Data-dependent accesses to memory are necessary for many real-world applications, but their cost remains prohibitive in secure computation. Prior work either focused on minimizing the need for data-dependent access in these applications, or reduced its cost by improving oblivious RAM for secure computation (SC-ORAM). Despite extensive efforts to improve SC-ORAM, the most concretely efficient solutions still require $\approx0.7$s per access to arrays of $2^{30}$ entries. This plainly precludes using MPC in a number of settings.

In this work, we take a pragmatic approach, exploring how concretely cheap MPC RAM access could be made if we are willing to allow one of the participants to learn the access pattern. We design a highly efficient Shared-Output Client-Server ORAM (SOCS-ORAM) that has constant overhead, uses one round-trip of interaction per access, and whose access cost is independent of array size. SOCS-ORAM is useful in settings with hard performance constraints, where one party in the computation is more trust-worthy and is allowed to learn the RAM access pattern. Our SOCS-ORAM is assisted by a third helper party that helps initialize the protocol and is designed for the honest-majority semi-honest corruption model.

We implement our construction in C++ and report its performance. For an array of length $2^{30}$ with $4$B entries, we communicate $13$B per access and take essentially no overhead beyond network latency.

Healthcare providers cannot share their patients' encrypted data among themselves because of interoperability issues. Many blockchain- based solutions have been proposed to allow for sharing medical data in a privacy-preserving manner, but interoperability problems persist. In this paper, we present a protocol called Blockchain-Format Preserving Encryption (B-FPE) to preserve patients' data privacy. Each patient is provided with an FPE key at the time of registration. All medical records are encrypted with the FPE key and stored in the blockchain. All the blockchain transactions are signed using group signatures. We use group signatures for signing the transactions to maintain the anonymity of healthcare providers. The new encrypted data block is concatenated to the blockchain. We present two cases: The regular phase, in which a patient is in a conscious state to share their FPE key with the healthcare provider, and the Emergency phase, in which a patient is not in a conscious state to share their key with the healthcare provider. In the latter case, the healthcare provider reconstructs the FPE key and decrypts the ciphertext. We assume this decryption happens in an oblivious manner.

Considering password-based authentication technique, password memorability is a real challenge on users. Hence, password reuse across different web applications is a common trend among users which makes websites vulnerable to credential stuffing attack. A solution as password manager helps the users to create random passwords for different websites on the user machine. However, it has practical challenges.

Password database breach detection is another related and challenging task. Among recent developments for breach detection, honeyword-based approach is much appreciated by the research community. However, honeyword generation itself is a challenging part of the solution.

In this work, we propose i) Password Reuse Detection (PRD) protocol for detecting password reuse using a secure two party private set intersection; ii) Breach Detection (BD) protocol that detects credential stuffing attacks using two party private set inclusion protocol based on random oblivious transfer. Both the proposals are designed for the authentication servers of the respective applications and need communication between multiple websites following the work by wang et al. Through analysis we show that our PRD protocol is around 2.8 times faster, and space efficient than existing works for 5000 honeywords. Our near to real-time BD protcol is around 2 times faster than existing works.

Fully homomorphic encryption (FHE) schemes are either lightweight and can evaluate boolean circuits or are relatively heavy and can evaluate arithmetic circuits on encrypted vectors, i.e., they perform single instruction multiple data operations (SIMD). SIMD FHE schemes can either perform exact modular arithmetic in the case of the Brakerski-Gentry-Vaikuntanathan (BGV) and Brakerski-Fan-Vercauteren (BFV) schemes or approximate arithmetic in the case of the Cheon-Kim-Kim-Song (CKKS) scheme. While one can homomorphically switch between BGV/BFV and CKKS using the computationally expensive bootstrapping procedure, it is unknown how to switch between these schemes without bootstrapping. Finding more efficient methods than bootstrapping of converting between these schemes was stated as an open problem by Halevi and Shoup, Eurocrypt 2015.

In this work, we provide strong evidence that homomorphic switching between BGV/BFV and CKKS is as hard as bootstrapping. In more detail, if one could efficiently switch between these SIMD schemes, then one could bootstrap these SIMD FHE schemes using a single call to a homomorphic scheme-switching algorithm without applying homomorphic linear transformations. Thus, one cannot hope to obtain significant improvements to homomorphic scheme-switching without also significantly improving the state-of-the-art for bootstrapping.

We also explore the relative hardness of computing homomorphic comparison in these same SIMD FHE schemes as a secondary contribution. We show that given a comparison algorithm, one can bootstrap these schemes using a few calls to the comparison algorithm for typical parameter settings. While we focus on the comparison function in this work, the overall approach to demonstrate relative hardness of computing specific functions homomorphically extends beyond comparison to other useful functions such as min/max or ReLU.

We propose a novel approach that utilizes fuzzification theory to perform feature selection on website content for encryption purposes. Our objective is to identify and select the most relevant features from the website by harnessing the principles of fuzzy logic. Fuzzification allows us to transform the crisp website content into fuzzy representations, enabling a more nuanced analysis of their characteristics. By considering the degree of membership of each feature in different fuzzy categories, we can evaluate their importance and relevance for encryption. This approach enables us to prioritize and focus on the features that exhibit higher membership degrees, indicating their significance in the encryption process. By employing fuzzification-based feature selection, we aim to enhance the effectiveness and efficiency of website content encryption, ultimately improving the overall internet security

Private-ID (PID) protocol enables two parties, each holding a private set of items, to privately compute a set of random universal identifiers (UID) corresponding to the records in the union of their sets, where each party additionally learns which UIDs correspond to which items in its set but not if they belong to the intersection or not. PID is very useful in the privacy computation of databases query, e.g. inner join and join for compute. Known PID protocols all assume the input of both parties is a set. In the case of join, a more common scenario is that one party's primary key (unique) needs to join the other party's foreign key (duplicate). How to construct an efficient Private Multiset ID (PMID) protocol to support the above \emph{key-foreign key join} remains open.

We resolve this problem by constructing efficient PMID protocols from Oblivious PRF, Private Set Union, and a newly introduced primitive called Deterministic-Value Oblivious Programmable PRF (dv-OPPRF). We also propose some PMID applications, including Private Inner Join, Private Full Join, and Private Join for Compute.

We implement our PMID protocols and state-of-the-art PID protocols as performance baselines. The experiments show that the performances of our PMID are almost the same as the state-of-the-art PIDs when we set the multiplicity $U_x = U_y = 1$. Our PMID protocols scale well when either $U_x > 1$ or $U_y > 1$. The performances also correctly reflect excessive data expansion when both $U_x, U_y > 1$ for the more general \emph{cross join} case.

In the permutation inversion problem, the task is to find the preimage of some challenge value, given oracle access to the permutation. This is a fundamental problem in query complexity, and appears in many contexts, particularly cryptography. In this work, we examine the setting in which the oracle allows for quantum queries to both the forward and the inverse direction of the permutation---except that the challenge value cannot be submitted to the latter. Within that setting, we consider two options for the inversion algorithm: whether it can get quantum advice about the permutation, and whether it must produce the entire preimage (search) or only the first bit (decision). We prove several theorems connecting the hardness of the resulting variations of the inversion problem, and establish a number of lower bounds. Our results indicate that, perhaps surprisingly, the inversion problem does not become significantly easier when the adversary is granted oracle access to the inverse, provided it cannot query the challenge itself.

A number of supersingular isogeny based cryptographic protocols require the endomorphism ring of the initial elliptic curve to be either unknown or random in order to be secure. To instantiate these protocols, Basso et al. recently proposed a secure multiparty protocol that generates supersingular elliptic curves defined over $\mathbb{F}_{p^2}$ of unknown endomorphism ring as long as at least one party acts honestly. However, there are many protocols that specifically require curves defined over $\mathbb{F}_p$, for which the Basso et al. protocol cannot be used. Also, the simple solution of using a signature scheme such as CSI-FiSh or SeaSign for proof of knowledge either requires extensive precomputation of large ideal class groups or is too slow for everyday applications.

In this paper, we present CSIDH-SCG, a new multiparty protocol that generates curves of unknown endomorphism ring defined over $\mathbb{F}_p$. This protocol relies on CSIDH-IP, a new CSIDH based proof of knowledge. We also present CSIDH-CR, a multiparty algorithm that be used in conjunction with CSIDH-SCG to generate a random curve over $\mathbb{F}_p$ while still keeping the endomorphism ring unknown.

Range searching is the problem of preprocessing a set of points $P$, such that given a query range $\gamma$ we can efficiently compute some function $f(P\cap\gamma)$. For example, in a 1 dimensional range counting query, $P$ is a set of numbers, $\gamma$ is a segment and we need to count how many numbers in $P$ are in $\gamma$. In higher dimensions, $P$ is a set of $d$ dimensional points and the query range is some volume in $R^d$. In general, we want to compute more than just counting, for example, the average of $P\cap\gamma$. Range searching has applications in databases where some SELECT queries can be translated to range searches. It had received a lot of attention in computational geometry where a data structure called partition tree was shown to solve range searching in time sub-linear in $|P|$ using only space linear in $|P|$.

In this paper we consider partition trees in a secure setting where we answer range queries without learning the value of the points or the parameters of the range. We show how partition trees can be securely traversed with $O(n^{1+\epsilon} + t \cdot n^{1-\frac{1}{d}+\epsilon})$ operations, where $n=|P|$, $t$ is the number of operations needed to compare to $\gamma$ and $\epsilon>0$ is a parameter. As far as we know, this is the first non-trivial bound on range searching and it improves over the na\"ive solution that needs $O(t\cdot n)$ operations.

Our algorithms are independent of the encryption scheme but as an example we implemented them using the CKKS FHE scheme. Our experiments show that for databases of sizes $2^{23}$ and $2^{25}$, our algorithms run $\times 2.8$ and $\times 4.7$ (respectively) faster than the naive algorithm.

The improvement of our algorithm comes from a method we call copy-and-recurse. With it we efficiently traverse a $r$-ary tree (where each inner node has $r$ children) that also has the property that at most $\xi$ of them need to be recursed into when traversing the tree. We believe this method is interesting in its own and can be used to improve traversals in other tree-like structures.

A possible new approach to the Zodiac Killer's 32-Character Cipher (Z32) is proposed based on the strengths and weaknesses of previous approaches and novel interpretations. This approach does not assume the use of anagrams or similar complex transposition methods; does not assume the identity of a particular Zodiac suspect; and assumes the use of homophonic substitution (as in Z408 and Z340), and simple transposition (as in Z340). Assumptions are clearly defined and tested with sensitivity tests. With Mount Diablo as the pole of a plane polar coordinate system, the instruction "set to Mag. N." is interpreted by setting the hour and minute hands of a watchface to the magnetic declination of the Bay Area circa 1970. Sensitivity tests reveal the exact year and location have little impact on the declination in this case. The hour and minute given by the hands are interpreted as the radial coordinate r and the angular coordinate theta, as in "Radians & # inches along the radians". The hand corresponding to each coordinate is tested, as are 12- and 24-hour interpretations. Impossible or improbable coordinates are excluded leaving one coordinate as a possible solution. This coordinate is explored as the possible plaintext for Z32 using the Z340 transposition method. Further exploration of the proposed method is necessary.

We present a reactive MPC protocol built from FHE which is robust in the presence of active adversaries. In addition the protocol enables reduced bandwidth via means of transciphering, and also enables more expressive/efficient programs via means of a $\mathsf{Declassify}$ operation. All sub-components of the protocol can be efficiently realised using existing technology. We prove our protocol secure in the UC framework.