Proxy re-encryption (PRE) allows a proxy with a re-encryption key to translate a ciphertext intended for Alice (delegator) to another ciphertext intended for Bob (delegatee) without revealing the underlying message. However, with PRE, Bob can obtain the whole message from the re-encrypted ciphertext, and Alice cannot take flexible control of the extent of the message transmitted to Bob. In this paper, we propose a new variant of PRE, called Fine-Grained PRE (FPRE), to support fine-grained re-encryptions. An FPRE is associated with a function family F, and each re-encryption key rk_{A→B}^f is associated with a function f ∈ F. With FPRE, Alice now can authorize re-encryption power to proxy by issuing rk_{A→B}^f to it, with f chosen by herself. Then the proxy can translate ciphertext encrypting m to Bob's ciphertext encrypting f(m) with such a fine-grained re-encryption key, and Bob only obtains a function of message m. In this way, Alice can take flexible control of the message spread by specifying functions. For FPRE, we formally define its syntax and formalize security notions including CPA security, ciphertext pseudo-randomness, unidirectionality, non-transitivity, collusion-safety under adaptive corruptions in the multi-user setting. Moreover, we propose a new security notion named ciphertext unlinkability, which blurs the link between a ciphertext and its re-encrypted ciphertext to hide the proxy connections between users. We establish the relations between those security notions. As for constructions, we propose two FPRE schemes, one for bounded linear functions and the other for deletion functions, based on the learning-with-errors (LWE) assumption. Our FPRE schemes achieve all the aforementioned desirable securities under adaptive corruptions in the standard model. As far as we know, our schemes provide the first solution to PRE with security under adaptive corruptions in the standard model.

We propose two generic constructions of public-key encryption (PKE) with tight simulation-based selective-opening security against chosen-ciphertext attacks (SIM-SO-CCA) in the random oracle model. Our constructions can be instantiated with a small constant number of elements in the ciphertext, ignoring smaller contributions from symmetric-key encryption. That is, they have compact ciphertexts. Furthermore, three of our instantiations have compact public keys as well. Known (almost) tightly SIM-SO-CCA secure PKE schemes are due to the work of Lyu et al. (PKC 2018) and Libert et al. (Crypto 2017). They have either linear-size ciphertexts or linear-size public keys. Moreover, they only achieve almost tightness, namely, with security loss depending on the security parameter. In contrast to them, our schemes are the first ones achieving both tight SIM-SO-CCA security and compactness. More precisely, our two generic constructions are: - From Pseudorandom KEM: Our first generic construction is from a key encapsulation mechanism (KEM) with pseudorandom ciphertexts against plaintext-checking attacks. Such a KEM can be constructed directly from the Strong Diffie-Hellman (StDH), Computational DH (CDH), and Decisional DH assumptions. Both their ciphertexts and public keys are compact. Their security loss is a small constant. Interestingly, our CDH-based construction is the first scheme achieving all these advantages based on a weak search assumption. Furthermore, we also give a generic construction of such a KEM, which yields an efficient tightly SIM-SO-CCA PKE from lattices. - From Lossy Encryption: Our second scheme is the well-known Fujisaki-Okamoto transformation. We show that it can turn a lossy encryption scheme into a tightly SIM-SO-CCA secure PKE. This transformation preserves both tightness and compactness of the underlying lossy encryption, which is in contrast to the non-tight proof of Heuer et al. (PKC 2015).

The Number Field Sieve and its numerous variants is the best algorithm to compute discrete logarithms in medium and large characteristic finite fields. When the extension degree $n$ is composite and the characteristic~$p$ is of medium size, the Tower variant (TNFS) is asymptotically the most efficient one. Our work deals with the last main step, namely the individual logarithm step, that computes a smooth decomposition of a given target~$T$ in the finite field thanks to two distinct phases: an initial splitting step, and a descent tree. In this article, we improve on the current state-of-the-art Guillevic's algorithm dedicated to the initial splitting step for composite~$n$. While still exploiting the proper subfields of the target finite field, we modify the lattice reduction subroutine that creates a lift in a number field of the target $T$. Our algorithm returns lifted elements with lower degrees and coefficients, resulting in lower norms in the number field. The lifted elements are not only much likely to be smooth because they have smaller norms, but it permits to set a smaller smoothness bound for the descent tree. Asymptotically, our algorithm is faster and works for a larger area of finite fields than Guillevic's algorithm, being now relevant even when the medium characteristic $p$ is such that $L_{p^n}(1/3) \leq p< L_{p^n}(1/2)$. In practice, we conduct experiments on $500$-bit and $2000$-bit composite finite fields: Our method becomes more efficient as the largest non trivial divisor of $n$ grows, being thus particularly adapted to even extension degrees.

We propose a new scheme based on ephemeral elliptic curves over the ring $\mathbb{Z}/n\mathbb{Z}$ where $n=pq$ is an RSA modulus with $p=u_p^2+v_p^2$, $q=u_q^2+v_q^2$, $u_p\equiv u_q\equiv 3\pmod 4$. The new scheme is a variant of both the RSA and the KMOV cryptosystems. The scheme can be used for both signature and encryption. We study the security of the new scheme and show that is immune against factorization attacks, discrete logarithm problem attacks, sum of two squares attacks, sum of four squares attacks, isomorphism attacks, and homomorphism attacks. Moreover, we show that the private exponents can be much smaller than the ordinary exponents for RSA and KMOV, which makes the decryption phase in the new scheme more efficient.

In this paper, we present NEV -- a faster and smaller NTRU Encryption using Vector decoding, which is provably IND-CPA secure in the standard model under the decisional NTRU and RLWE assumptions over the cyclotomic ring $R_q = \mathbb{Z}_q[X]/(X^n+1)$. Our main technique is a novel and non-trivial way to integrate a previously known plaintext encoding and decoding mechanism into the provably IND-CPA secure NTRU variant by Stehl\'e and Steinfeld (Eurocrypt 2011). Unlike the original NTRU encryption and its variants which encode the plaintext into the least significant bits of the coefficients of a message polynomial, we encode each plaintext bit into the most significant bits of multiple coefficients of the message polynomial, so that we can use a vector of noised coefficients to decode each plaintext bit in decryption, and significantly reduce the size of $q$ with a reasonably negligible decryption failure. Concretely, we can use $q = 769$ to obtain public keys and ciphertexts of 615 bytes with decryption failure $\leq 2^{-138}$ at NIST level 1 security, and 1229 bytes with decryption failure $\leq 2^{-152}$ at NIST level 5 security. By applying the Fujisaki-Okamoto transformation in a standard way, we obtain an IND-CCA secure KEM from our basic PKE scheme. Compared to NTRU and Kyber in the NIST Round 3 finalists at the same security levels, our KEM is 33-48% more compact and 5.03-29.94X faster than NTRU in the round-trip time of ephemeral key exchange, and is 21% more compact and 1.42-1.74X faster than Kyber. We also give an optimized encryption scheme NEV' with better noise tolerance (and slightly better efficiency) based on a variant of the RLWE problem, called Subset-Sum Parity RLWE problem, which we show is polynomially equivalent to the standard decisional RLWE problem (with different parameters), and maybe of independent interest.

In this paper a method to build Secret Agreement algorithms is pre- sented, which only requires an abelian group and at least one automor- phism of the operator of this group. An example of such an algorithm is also presented. Knowledge of entropic quasigroups and Bruck-Murdoch- Toyoda theorem on how to build a quasigroup with these two elements is assumed.

Homomorphic encryption (HE) has opened an entirely new world up in the privacy-preserving use of sensitive data by conducting computations on encrypted data. Amongst many HE schemes targeting computation in various contexts, Cheon--Kim--Kim--Song (CKKS) scheme is distinguished since it allows computations for encrypted real number data, which have greater impact in real-world applications. CKKS scheme is a levelled homomorphic encryption scheme, consuming one level for each homomorphic multiplication. When the level runs out, a special computational circuit called bootstrapping is required in order to conduct further multiplications. The algorithm proposed by Cheon et al. has been regarded as a standard way to do bootstrapping in the CKKS scheme, and it consists of the following four steps: ModRaise, CoeffToSlot, EvalMod and SlotToCoeff. However, the steps consume a number of levels themselves, and thus optimizing this extra consumption has been a major focus of the series of recent research. Among the total levels consumed in the bootstrapping steps, about a half of them is spent in CoeffToSlot and SlotToCoeff steps to scale up the real number components of DFT matrices and round them to the nearest integers. Each scale-up factor is very large so that it takes up one level to rescale it down. Scale-up factors can be taken smaller to save levels, but the error of rounding would be transmitted to EvalMod and eventually corrupt the accuracy of bootstrapping. EvalMod aims to get rid of the superfluous $qI$ term from a plaintext $pt + qI$ resulting from ModRaise, where $q$ is the bottom modulus and $I$ is a polynomial with small integer coefficients. EvalRound is referred to as its opposite, obtaining $qI$. We introduce a novel bootstrapping algorithm consisting of ModRaise, CoeffToSlot, EvalRound and SlotToCoeff, which yields taking smaller scale-up factors without the damage of rounding errors.

QC-MDPC (quasi cyclic moderate density parity check) code-based McEliece cryptosystems are considered to be one of the candidates for post-quantum cryptography. Decreasing DER (decoding error rate) is one of important factor for their security, since recent attacks to these cryptosystems effectively use DER information. In this paper, we pursue the possibility of optimization-base decoding, concretely we examine ADMM (alternating direction method of multipliers), a recent developing method in optimization theory. Further, RSPA (reproducing sum-product algorithm), which efficiently reuse outputs of SPA (sum-product algorithm) is proposed for the reduction of execution time in decoding. By numerical simulations, we show that the proposing scheme shows considerable decrement in DER compared to the conventional decoding methods such as BF (bit-flipping algorithm) variants or SPA.

Attribute-based encryption (ABE) is a popular type of public-key encryption that enforces access control cryptographically, and has spurred the proposal of many use cases. To satisfy the requirements of the setting, tailor-made schemes are often introduced. However, designing secure schemes---as well as verifying that they are secure---is notoriously hard. Several of these schemes have turned out to be broken, making them dangerous to deploy in practice. To overcome these shortcomings, we introduce ACABELLA. ACABELLA simplifies generating and verifying security proofs for pairing-based ABE schemes. It consists of a framework for security proofs that are easy to verify manually and an automated tool that efficiently generates these security proofs. Creating such security proofs generally takes no more than a few seconds. The output is easy to understand, and the proofs can be verified manually. In particular, the verification of a security proof generated by ACABELLA boils down to performing simple linear algebra. The ACABELLA tool is open source and also available via a web interface. With its help, experts can simplify their proof process by verifying or refuting the security claims of their schemes and practitioners can get an assurance that the ABE scheme of their choice is secure.

This paper introduces Brakedown, the first built system that provides linear-time SNARKs for NP, meaning the prover incurs $O(N)$ finite field operations to prove the satisfiability of an $N$-sized R1CS instance. Brakedown’s prover is faster, both concretely and asymptotically, than prior SNARK implementations. Brakedown does not require a trusted setup and is plausibly post-quantum secure. Furthermore, it is compatible with arbitrary finite fields of sufficient size; this property is new amongst implemented arguments with sublinear proof sizes. To design Brakedown, we observe that recent work of Bootle, Chiesa, and Groth (BCG, TCC 2020) provides a polynomial commitment scheme that, when combined with the linear-time interactive proof system of Spartan (CRYPTO 2020), yields linear-time IOPs and SNARKs for R1CS (a similar theoretical result was previously established by BCG, but our approach is conceptually simpler, and crucial for achieving high-speed SNARKs). A core ingredient in the polynomial commitment scheme that we distill from BCG is a linear-time encodable code. Existing constructions of such codes are believed to be impractical. Nonetheless, we design and engineer a new one that is practical in our context. We also implement a variant of Brakedown that uses Reed-Solomon codes instead of our linear-time encodable codes; we refer to this variant as Shockwave. Shockwave is not a linear-time SNARK, but it provides shorter proofs and lower verification times than Brakedown (it also provides a faster prover than prior plausibly post-quantum SNARKs).

In PKC 2014, a policy-based signature (PBS) scheme was proposed by Bellare and Fuchsbauer in which a signer can only sign messages conforming to some policy specified by an issuing authority. PBS construction supports the delegation of signing policy keys with possible restrictions to the original policy. Although the PBS scheme is meant to restrict the signing privileges of the scheme’s users, singers could easily share their signing keys with others without being held accountable since PBS does not have a tracing capability, and a signing policy key defines a policy that should be satisfied by the message only. In this work, we build on PBS and propose a traceable policy-based signature scheme (TPBS) where we employ a rerandomizable signature scheme, a digital signature scheme, and a zero-knowledge proof system as its building blocks. TPBS introduces the notion of anonymized identity keys that are used with the policy keys for signing. Thus it achieves traceability without compromising the delegatability feature of the PBS scheme. Additionally, TPBS ensures non-frameability under the assumption of a corrupted tracing authority. We define and formally prove the security notions of the generic TPBS scheme. Finally, we propose an instantiation of TPBS utilizing the Pointcheval Sanders rerandomizable signature scheme, Abe et al.’s structure-preserving signature scheme, and Groth-Sahai NIZK system, and analyze its efficiency.

Threshold signatures are digital signature schemes in which a set of $n$ signers specify a threshold $t$ such that any subset of size $t$ is authorized to produce signatures on behalf of the group. There has recently been a renewed interest in this primitive, largely driven by the need to secure highly valuable signing keys, e.g., DNSSEC keys or keys protecting digital wallets in the cryptocurrency ecosystem. Of special interest is FROST, a practical Schnorr threshold signature scheme, which is currently undergoing standardization in the IETF and whose security was recently analyzed at CRYPTO'22. We continue this line of research by focusing on FROST's unforgeability combined with a practical distributed key generation (DKG) algorithm. Existing proofs of this setup either use non-standard heuristics, idealized group models like the AGM, or idealized key generation. Moreover, existing proofs do not consider all practical relevant optimizations that have been proposed. We close this gap between theory and practice by presenting the Schnorr threshold signature scheme Olaf, which combines the most efficient known FROST variant FROST3 with a variant of Pedersen's DKG protocol (as commonly used for FROST), and prove its unforgeability. Our proof relies on the AOMDL assumption (a weaker and falsifiable variant of the OMDL assumption) and, like proofs of regular Schnorr signatures, on the random oracle model.

Orientations of supersingular elliptic curves encode the information of an endomorphism of the curve. Computing the full endomorphism ring is a known hard problem, so one might consider how hard it is to find one such orientation. We prove that access to an oracle which tells if an elliptic curve is $\mathfrak{O}$-orientable for a fixed imaginary quadratic order $\mathfrak{O}$ provides non-trivial information towards computing an endomorphism corresponding to the $\mathfrak{O}$-orientation. We provide explicit algorithms and in-depth complexity analysis. We also consider the question in terms of quaternion algebras. We provide algorithms which compute an embedding of a fixed imaginary quadratic order into a maximal order of the quaternion algebra ramified at $p$ and $\infty$. We provide code implementations in Sagemath which is efficient for finding embeddings of imaginary quadratic orders of discriminants up to $O(p)$, even for cryptographically sized $p$.

The pseudorandom sampling of constant weight words, as it is currently implemented in cryptographic schemes like BIKE or HQC, is prone to the leakage of information on the seed being used for the pseudorandom number generation. This creates a vulnerability when the semantic security conversion requires a deterministic re-encryption. This observation was first made in [HLS21] about HQC and a timing attack was presented to recover the secret key. As suggested in [HLS21] a similar attack applies to BIKE and instances of such an attack were presented in an earlier version of this work [Sen21] and independently in [GHJ+22]. The timing attack stems from the variation of the amount of pseudorandom data to draw and process for sampling uniformly a constant weight word. We give here the exact distribution of this amount for BIKE. This will allow us to estimate precisely the cost of the natural countermeasure which consists in drawing always the same (large enough) amount of randomness for the sampler to terminate with probability overwhelmingly close to one. The main contribution of this work is to suggest a new approach for fixing the issue. It is first remarked that, contrary to what is done currently, the sampling of constant weight words doesn't need to produce a uniformly distributed output. If the distribution is close to uniform in the appropriate metric, the impact on security is negligible. Also, a new variant of the Fisher-Yates shuffle is proposed which is (1) very well suited for secure implementations against timing and cache attacks, and (2) produces constant weight words with a distribution close enough to uniform.

The question of whether public-key encryption (PKE) can be constructed from the assumption that one-way functions (OWF) exist remains a central open problem. In this paper we give two constructions of bit PKE scheme derived from any NP language L, along with a polynomial-time instance-witness sampling algorithm. Furthermore, we prove that if L is average hard NP language, the the presented schemes is CPA secure. Our results give a positive answer to this longstanding problem, as the existence of OWF implies the existence of average hard NP language with a polynomial-time instance-witness sampling algorithm. Additionally, we obtain a witness encryption (WE) scheme for NP language based on the presented PKE scheme. This result highlights that WE scheme can also be established based on the existence of OWF.

In this paper, we construct the first provably-secure isogeny-based (partially) blind signature scheme. While at a high level the scheme resembles the Schnorr blind signature, our work does not directly follow from that construction, since isogenies do not offer as rich an algebraic structure. Specifically, our protocol does not fit into the "linear identification protocol" abstraction introduced by Hauck, Kiltz, and Loss (EUROCYRPT'19), which was used to generically construct Schnorr-like blind signatures based on modules such as classical groups and lattices. Consequently, our scheme is provably-secure in the poly-logarithmic (in the number of security parameter) concurrent execution and does not seem susceptible to the recent efficient ROS attack exploiting the linear nature of the underlying mathematical tool. In more detail, our blind signature exploits the "quadratic twist" of an elliptic curve in an essential way to endow isogenies with a strictly richer structure than abstract group actions (but still more restrictive than modules). The basic scheme has public key size $128$~B and signature size $8$~KB under the CSIDH-512 parameter sets---these are the smallest among all provably secure post-quantum secure blind signatures. Relying on a new "ring" variant of the group action inverse problem rGAIP, we can halve the signature size to 4~KB while increasing the public key size to 512~B. We provide preliminary cryptanalysis of rGAIP and show that for certain parameter settings, it is essentially as secure as the standard GAIP. Finally, we show a novel way to turn our blind signature into a partially blind signature, where we deviate from prior methods since they require hashing into the set of public keys while hiding the corresponding secret key---constructing such a hash function in the isogeny setting remains an open problem.

In this paper, we propose a noncommutative-ring based unbalanced oil and vinegar signature scheme with key-randomness alignment: NOVA (Noncommutative Oil and Vinegar with Alignment). Instead of fields or even commutative rings, we show that noncommutative rings can be used for algebraic cryptosystems. At the same or better level of security requirement, NOVA has a much smaller public key than UOV (Unbalanced Oil and Vinegar), which makes NOVA practical in most situations. We use Magma to actually implement and give a detailed security analysis against known major attacks.

In this work, we construct the first digital signature (SIG) and public-key encryption (PKE) schemes with almost tight multi-user security under adaptive corruptions based on the learning-with-errors (LWE) assumption in the standard model. Our PKE scheme achieves almost tight IND-CCA security and our SIG scheme achieves almost tight strong EUF-CMA security, both in the multi-user setting with adaptive corruptions. The security loss is quadratic in the security parameter, and independent of the number of users, signatures or ciphertexts. Previously, such schemes were only known to exist under number-theoretic assumptions or in classical random oracle model, thus vulnerable to quantum adversaries. To obtain our schemes from LWE, we propose new frameworks for constructing SIG and PKE with a core technical tool named probabilistic quasi-adaptive hash proof system (pr-QA-HPS). As a new variant of HPS, our pr-QA-HPS provides probabilistic public and private evaluation modes that may toss coins. This is in stark contrast to the traditional HPS [Cramer and Shoup, Eurocrypt 2002] and existing variants like approximate HPS [Katz and Vaikuntanathan, Asiacrypt 2009], whose public and private evaluations are deterministic in their inputs. Moreover, we formalize a new property called evaluation indistinguishability by requiring statistical indistinguishability of the two probabilistic evaluation modes, even in the presence of the secret key. The evaluation indistinguishability, as well as other nice properties resulting from the probabilistic features of pr-QA-HPS, are crucial for the multi-user security proof of our frameworks under adaptive corruptions. As for instantiations, we construct pr-QA-HPS from the LWE assumption and prove its properties with almost tight reductions, which admit almost tightly secure LWE-based SIG and PKE schemes under our frameworks. Along the way, we also provide new almost-tight reductions from LWE to multi-secret LWE, which may be of independent interest.

We fix an omission in [Petit17] on torsion point attacks of isogeny-based cryptosystems akin to SIDH, also reprised in [dQuehen-etal21]. In these works, their authors represent certain integers using a norm equation to derive a secret isogeny. However, this derivation uses as a crucial ingredient ([Petit17] Section 4.3), which we show to be incorrect. We then state sufficient conditions allowing to prove a modified version this lemma. A further idea of parametrizing solutions of the norm equation will show that these conditions can be fulfilled under the same heuristics of these previous works. Our contribution is a theoretical one. It doesn't invalidate the attack, which works as well in practice, but gives a correct mathematical justification for it. We also simplify the argument of Theorem 3 in [dQuehen-etal21] to show that the requirement that $m$ be small is unnecessary.

Both threshold and blind signatures have, individually, received a considerable amount of attention. However little is known about their combination, i.e., a threshold signature which is also blind, in that no coalition of signers learns anything about the message being signed or the signature being produced. Several applications of blind signatures (e.g., anonymous tokens) would benefit from distributed signing as a means to increase trust in the service and hence reduce the risks of key compromise. This paper builds the first blind threshold signatures in pairing-free groups. Our main contribution is a construction that transforms an underlying blind non-threshold signature scheme with a suitable structure into a threshold scheme, preserving its blindness. The resulting signing protocol proceeds in three rounds, and produces signatures consisting of one group element and two scalars. The underlying non-threshold blind signature schemes are of independent interest, and improve upon the current state of the art (Tessaro and Zhu, EUROCRYPT ’22) with shorter signatures (three elements, instead of four) and simpler proofs of security. All of our schemes are proved secure in the Random Oracle and Algebraic Group Models, assuming the hardness of the discrete logarithm problem.

In this paper, we study the decoding failure rate (DFR) of non-binary QC-MDPC codes using theoretical tools, extending the results of previous binary QC-MDPC code studies. The theoretical estimates of the DFR are particularly significant for cryptographic applications of QC-MDPC codes. Specifically, in the binary case, it is established that exploiting decoding failures makes it possible to recover the secret key of a QC-MDPC cryptosystem. This implies that to attain the desired security level against adversaries in the CCA2 model, the decoding failure rate must be strictly upper-bounded to be negligibly small. In this paper, we observe that this attack can also be extended to the non--binary case as well, which underscores the importance of DFR estimation. Consequently, we study the guaranteed error-correction capability of non-binary QC-MDPC codes under one-step majority logic (OSML) decoder and provide a theoretical analysis of the 1-iteration parallel symbol flipping decoder and its combination with OSML decoder. Utilizing these results, we estimate the potential public-key sizes for QC-MDPC cryptosystems over $\mathbb{F}_4$ for various security levels. We find that there is no advantage in reducing key sizes when compared to the binary case.

NTRU was the first practical public key encryption scheme constructed on a lattice over a polynomial-based ring and has been considered secure against significant cryptanalytic attacks over the past few decades. However, NTRU and its variants suffer from several drawbacks, including difficulties in achieving worst-case correctness error in a moderate modulus, inconvenient sampling distributions for messages, and relatively slower algorithms compared to other lattice-based schemes. In this work, we propose a new NTRU-based key encapsulation mechanism (KEM), called NTRU+, which overcomes nearly all existing drawbacks. NTRU+ is constructed based on two new generic transformations: $\mathsf{ACWC}_{2}$ and $\overline{\mathsf{FO}}^{\perp}$ (a variant of the Fujisaki-Okamoto transform). $\mathsf{ACWC}_{2}$ is used to easily achieve worst-case correctness error, while $\overline{\mathsf{FO}}^{\perp}$ is used to achieve chosen-ciphertext security without re-encryption. Both $\mathsf{ACWC}_{2}$ and $\overline{\mathsf{FO}}^{\perp}$ are defined using a randomness-recovery algorithm and an encoding method. In particular, our simple encoding method, the semi-generalized one-time pad (SOTP), allows us to sample a message from a natural bit-string space with an arbitrary distribution. We provide four parameter sets for NTRU+ and present implementation results using NTT-friendly rings over cyclotomic trinomials.

Recently, some studies have constructed one-coordinate arithmetics on elliptic curves. For example, formulas of the $x$-coordinate of Montgomery curves, $x$-coordinate of Montgomery$^-$ curves, $w$-coordinate of Edwards curves, $w$-coordinate of Huff's curves, $\omega$-coordinates of twisted Jacobi intersections have been proposed. These formulas are useful for isogeny-based cryptography because of their compactness and efficiency. In this paper, we define a novel function on elliptic curves called the generalized Montgomery coordinate that has the five coordinates described above as special cases. For a generalized Montgomery coordinate, we construct an explicit formula of scalar multiplication that includes the division polynomial, and both a formula of an image point under an isogeny and that of a coefficient of the codomain curve. Finally, we present two applications of the theory of a generalized Montgomery coordinate. The first one is the construction of a new efficient formula to compute isogenies on Montgomery curves. This formula is more efficient than the previous one for high degree isogenies as the $\sqrt{\vphantom{2}}$\'{e}lu's formula in our implementation. The second one is the construction of a new generalized Montgomery coordinate for Montgomery$^-$ curves used for CSURF.

Recently, Abdalla, Gong and Wee (Crypto 2020) provided the first functional encryption scheme for attribute-weighted sums (AWS), where encryption takes as input $N$ (unbounded) attribute-value pairs $\{\vec{x}_i, \vec{z}_i\}_{I \in [N]}$ where $\vec{x}_i$ is public and $\vec{z}_i$ is private, the secret key is associated with an arithmetic branching programs $f$, and decryption returns the weighted sum ${\sum}_{{i \in [N]}} f(\vec{x}_i)^\top \vec{z}_i$, leaking no additional information about the $\vec{z}_i$'s. We extend FE for AWS to the significantly more challenging multi-party setting and provide the first construction for {\it attribute-based} multi-input FE (MIFE) supporting AWS. For $i \in [n]$, encryptor $i$ can choose an attribute $\vec{y}_i$ together with AWS input $\{\vec{x}_{i,j}, \vec{z}_{i,j}\}$ where $j \in [N_i]$ and $N_i$ is unbounded, the key generator can choose an access control policy $g_i$ along with its AWS function $h_i$ for each $i \in [n]$, and the decryptor can compute $$\sum_{i \in [n]}\sum_{j \in [N_{i}]}h_{i}(\vec{x}_{i,j})^{\top}\vec{z}_{i,j} \text{ iff } g_{i}(\vec{y}_{i}) =0 \text{ for all } i \in [n]$$ Previously, the only known attribute based MIFE was for the inner product functionality (Abdalla et al.~Asiacrypt 2020), where additionally, $\vec{y}_i$ had to be fixed during setup and must remain the same for all ciphertexts in a given slot. Our attribute based MIFE implies the notion of multi-input {\it attribute based encryption} (\miabe) recently studied by Agrawal, Yadav and Yamada (Crypto 2022) and Francati, Friolo, Malavolta and Venturi (Eurocrypt 2023), for a conjunction of predicates represented as arithmetic branching programs (ABP). Along the way, we also provide the first constructions of multi-client FE (MCFE) and dynamic decentralized FE (DDFE) for the AWS functionality. Previously, the best known MCFE and DDFE schemes were for inner products (Chotard et al.~ePrint 2018, Abdalla, Benhamouda and Gay, Asiacrypt 2019, and Chotard et al.~Crypto 2020). Our constructions are based on pairings and proven selectively secure under the matrix DDH assumption.

Pairings are useful tools in isogeny-based cryptography and have been used in SIDH/SIKE and other protocols. As a general technique, pairings can be used to move problems about points on curves to elements in finite fields. However, until now, their applicability was limited to curves over fields with primes of a specific shape and pairings seemed too costly for the type of primes that are nowadays often used in isogeny-based cryptography. We remove this roadblock by optimizing pairings for highly-composite degrees such as those encountered in CSIDH and SQISign. This makes the general technique viable again: We apply our low-cost pairing to problems of general interest, such as supersingularity verification and finding full-torsion points, and show that we can outperform current methods, in some cases up to four times faster than the state-of-the-art. Furthermore, we analyze how pairings can be used to improve deterministic and dummy-free CSIDH. Finally, we provide a constant-time implementation (in Rust) that shows the practicality of these algorithms.

In this work, we first present general methods to construct information rate-1 PKE that is $\KDM^{(n)}$-secure with respect to \emph{block-affine} functions for any unbounded polynomial $n$. To achieve this, we propose a new notion of extractor that satisfies \emph{reusability}, \emph{homomorphic}, and \emph{security against correlated-source attacks}, and show how to use this extractor to improve the information rate of the \KDM-secure PKE of Brakerski et al.~(Eurocrypt 18). Then, we show how to amplify \KDM~security from block-affine function class into general bounded size circuits via a variant of the technique of Applebaum (Eurocrypt 11), achieving better efficiency. Furthermore, we show how to generalize these approaches to the IBE setting. Additionally, our PKE and IBE schemes are also leakage resilient, with leakage rates $1-o(1)$ against a slightly smaller yet still general class -- block leakage functions. We can instantiate the required building blocks from $\LWE$ or $\DDH$.

A linkable ring signature allows a user to sign anonymously on behalf of a group while ensuring that multiple signatures from the same user are detected. Applications such as privacy-preserving e-voting and e-cash can leverage linkable ring signatures to significantly improve privacy and anonymity guarantees. To scale to systems involving large numbers of users, short signatures with fast verification are a must. Concretely efficient ring signatures currently rely on a trusted authority maintaining a master secret, or follow an accumulator-based approach that requires a trusted setup. In this work, we construct the first linkable ring signature with both logarithmic signature size and verification that does not require any trusted mechanism. Our scheme, which relies on discrete-log type assumptions and bilinear maps, improves upon a recent concise ring signature called DualRing by integrating improved preprocessing arguments to reduce the verification time from linear to logarithmic in the size of the ring. Our ring signature allows signatures to be linked based on what message is signed, ranging from linking signatures on any message to only signatures on the same message. We provide benchmarks for our scheme and prove its security under standard assumptions. The proposed linkable ring signature is particularly relevant to use cases that require privacy-preserving enforcement of threshold policies in a fully decentralized context, and e-voting.

In spite of the wave of devastating attacks on SIDH, started by Castryck-Decru (Eurocrypt 2023), there is still interest in constructing quantum secure SIDH Proofs of Knowledge (PoKs). For instance, SIDH PoKs for the Fixed Degree Relation, aim to prove the knowledge of a fixed degree d isogeny ω between the elliptic curve E0 and the public keys E1, E2. In such cases, the public keys consist of only the elliptic curves (without image of auxiliary points), which suggests that the Castryck- Decru-like attack does not apply these scenarios. In this paper we focus on the SIDH proof of knowledge of De Feo, Dobson, Galbraith, and Zobernig (Asiacrypt 2022); more precisely, we focus on their first 3-special soundness construction. In this work, we explicitly describe an optimized recoverable Σ-protocol based on their 3-special soundness SIDH-PoK. We also analyze the impact of building a signature scheme based on the optimized protocol and study the impact of moving to B-SIDH and G2SIDH setups, on the signature sizes.

A universal re-encryption (URE) scheme is a public-key encryption scheme enhanced with an algorithm that on input a ciphertext, outputs another ciphertext which is still a valid encryption of the underlying plaintext. Crucially, such a re-encryption algorithm does not need any key as input, but the ciphertext is guaranteed to be valid under the original key-pair. Therefore, URE schemes lend themselves naturally as building blocks of mixnets: A sender transmits the encryption of a message under the receivers public-key to a mixer, which re-encrypts it, and the receiver later retrieves the re-encrypted ciphertext, which will decrypt successfully to the original message. Young and Yung (SCN 2018) argued that the original definition of URE by Golle et al. (CT-RSA 2004) was flawed, because it did not consider anonymity of encryption. This motivated them to claim that they finally put URE on solid grounds by presenting four formal security notions which they argued a URE should satisfy. As our first contribution, we introduce a framework that allows to compactly define and relate security notions as substitutions of systems. Using such framework, as our second contribution we show that Young and Yung's four notions are not minimal, and therefore do not properly capture the essence of a secure URE scheme. We provide three definitions that imply (and are implied by) theirs. Using the constructive cryptography framework, our third contribution is to capture the essence of URE from an application point of view by providing a composable security notion that expresses the ideal use of URE in a mixnet. Finally, we show that the composable notion is implied by our three minimal notions.

We present a framework for building practical anonymous credential schemes based on the hardness of lattice problems. The running time of the prover and verifier is independent of the number of users and linear in the number of attributes. The scheme is also compact in practice, with the proofs being as small as a few dozen kilobytes for arbitrarily large (say up to $2^{128}$) users with each user having several attributes. The security of our scheme is based on a new family of lattice assumptions which roughly states that given short pre-images of random elements in some set $S$, it is hard to create a pre-image for a fresh element in such a set. We show that if the set admits efficient zero-knowledge proofs of knowledge of a commitment to a set element and its pre-image, then this yields practically-efficient privacy-preserving primitives such as blind signatures, anonymous credentials, and group signatures. We propose a candidate instantiation of a function from this family which allows for such proofs and thus yields practical lattice-based primitives.

Private payments in blockchain-based cryptocurrencies have been a topic of research, both academic and industrial, ever since the advent of Bitcoin. Stealth address payments were proposed as a solution to improve payment privacy for users and are, in fact, deployed in several major cryptocurrencies today. The mechanism lets users receive payments so that none of these payments are linkable to each other or the recipient. Currently known stealth address mechanisms either (1) are insecure in certain reasonable adversarial models, (2) are inefficient in practice or (3) are incompatible with many existing currencies. In this work, we formalize the underlying cryptographic abstraction of this mechanism, namely, stealth signatures with formal game-based definitions. We show a surprising application of our notions to passwordless authentication defined in the Fast IDentity Online (FIDO) standard. We then present SPIRIT, the first efficient post-quantum secure stealth signature construction based on the NIST standardized signature and key-encapsulation schemes, Dilithium and Kyber. The basic form of SPIRIT is only secure in a weak security model, but we provide an efficiency-preserving and generic transform, which boosts the security of SPIRIT to guarantee the strongest security notion defined in this work. Compared to state-of-the-art, there is an approximately 800x improvement in the signature size while keeping signing and verification as efficient as 0.2 ms. We extend SPIRIT with a fuzzy tracking functionality where recipients can outsource the tracking of incoming transactions to a tracking server, satisfying an anonymity notion similar to that of fuzzy message detection (FMD) recently introduced in [CCS 2021]. We also extend SPIRIT with a new fuzzy tracking framework called scalable fuzzy tracking that we introduce in this work. This new framework can be considered as a dual of FMD, in that it reduces the tracking server's computational workload to sublinear in the number of users, as opposed to linear in FMD. Experimental results show that, for millions of users, the server only needs 3.4 ms to filter each incoming message which is a significant improvement upon the state-of-the-art.

This draft presents work-in-progress concerning hybrid/composite signature schemes. More concretely, we give several tailored combinations of Fiat-Shamir based signature schemes (such as Dilithium) or Falcon with RSA or DSA. We observe that there are a number of signature hybridization goals, few of which are not achieved through parallel signing or concatenation approaches. These include proof composability (that the post-quantum hybrid signature security can easily be linked to the component algorithms), weak separability, strong separability, backwards compatibility, hybrid generality (i.e., hybrid compositions that can be instantiated with different algorithms once proven to be secure), and simultaneous verification. We do not consider backwards compatibility in this work, but aim in our constructions to show the feasibility of achieving all other properties. As a work-in-progress, the constructions are presented without the accompanying formal security analysis, to be included in an update.

The Hidden Number Problem (HNP) has been extensively used in the side-channel attacks against (EC)DSA and Diffie-Hellman. The lattice approach is a primary method of solving the HNP. In EUROCRYPT 2021, Albrecht and Heninger constructed a new lattice to solve the HNP, which converts the HNP to the SVP. After that, their approach became the state-of-the-art lattice method of solving the HNP. But Albrecht and Heninger's approach has a high failure rate for solving the HNP with one bit of nonce ($1$-bit HNP) because there are enormous vectors related to the modulus $q$ shorter than the target vector in Albrecht and Heninger's Lattice. To decrease the number of vectors that are shorter than the target vector and avoid the duplicated reduction, we introduce the modulo-$q$ lattice, a residue class ring of the general lattice modulo $q$, where $q$ is the modulus of the HNP. We present a new sieving algorithm to search for the shortest vectors in the modulo-$q$ lattice. Our algorithm uses built-in modulo $q$ arithmetic and many optimization techniques. As a result, we can solve a general 1-bit HNP ($q=2^{120}$) within 5 days and solve a general 1-bit HNP ($q=2^{128}$) within 17 days.

Multi-signatures (MS) are a special type of public key signature (PKS) in which multiple signers participate cooperatively to generate a signature for a single message. Recently, applications that use an MS scheme to strengthen the security of blockchain wallets or to strengthen the security of blockchain consensus protocols are attracting a lot of attention. In this paper, we propose an efficient two-round MS scheme based on Okamoto signatures rather than Schnorr signatures. To this end, we first propose a new PKS scheme by modifying the Okamoto signature scheme, and prove the unforgeability of our PKS scheme under the discrete logarithm assumption in the algebraic group model (AGM) and the non-programmable random oracle model (ROM). Next, we propose a two-round MS scheme based on the new PKS scheme and prove the unforgeability of our MS scheme under the discrete logarithm assumption in the AGM and the non-programmable ROM. Our MS scheme is the first one to prove security among two-round MS based on Okamoto signature.

The problem of solving a system of multivariate quadratic equations over a finite field is known to be hard in general. However, there have been several algorithms of solving the system of quadratic equations efficiently when the number of variables is sufficiently larger than the number of equations (e.g., Kipnis et al., Eurocrypt 1999, Thomae-Wolf, PKC 2012, Cheng et al., PQCrypto 2014 and Furue et al., PQCrypto 2021). In the present paper, we propose a new algorithm which is available if the number of variables is smaller than that required in the previously given algorithms. We also analyze the security of MAYO, a variant of UOV, proposed in SAC 2021 and submitted to NIST's standardization project of additional digital signature schemes for Post-Quantum Cryptography.

This paper explores the use of a system of equations to factor semiprime numbers. Semiprime numbers are a special type of omposite number that are the product of two prime numbers. Factoring semiprime numbers is important in cryptography and number theory. In this study, we present a method that applies a system of polynomial equations to factor semiprime number $M$. Where $M$ can be any semiprime number. In fact, we build a family of systems where each system compose from three polynomial equations with three variables. The results of this study show that a solution for one system results with a complete factorization for a semiprime number. It may be possible to apply well known algorithms, such as Grobner method to solve one of those systems for a particular semiprime number $M$.

The quantum resistance Key Encapsulation Mechanism (PQC-KEM) design aims to replace cryptography in legacy security protocols. It would be nice if PQC-KEM were faster and lighter than ECDH or DH for easy migration to legacy security protocols. However, it seems impossible due to the temperament of the secure underlying problems in a quantum environment. Therefore, it makes reason to determine the threshold of the scheme by analyzing the maximum bandwidth the legacy security protocol can adapt. We specified the bandwidth threshold at 1,244 bytes based on IKEv2 (RFC7296), a security protocol with strict constraints on payload size in the initial exchange for secret key sharing. We propose TiGER that is an IND-CCA secure KEM based on RLWE(R). TiGER has a ciphertext (1,152bytes) and a public key (928 bytes) smaller than 1,244 bytes, even at the AES256 security level. To our knowledge, TiGER is the only scheme with such an achievement. Also, TiGER satisfies security levels 1, 3, and 5 of NIST competition. Based on reference implementation, TiGER is 1.7-2.6x faster than Kyber and 2.2-4.4x faster than LAC.

This article explores the connection between radical isogenies and modular curves. Radical isogenies are formulas designed for the computation of chains of isogenies of fixed small degree $N$, introduced by Castryck, Decru, and Vercauteren at Asiacrypt 2020. One significant advantage of radical isogeny formulas over other formulas with a similar purpose is that they eliminate the need to generate a point of order $N$ that generates the kernel of the isogeny. While radical isogeny formulas were originally developed using elliptic curves in Tate normal form, Onuki and Moriya have proposed radical isogeny formulas of degrees $3$ and $4$ on Montgomery curves and attempted to obtain a simpler form of radical isogenies using enhanced elliptic and modular curves. In this article, we translate the original setup of radical isogenies in Tate normal form into the language of modular curves. Additionally, we solve an open problem introduced by Onuki and Moriya regarding radical isogeny formulas on $X_0(N).$

We propose UniPlonK, a modification of the PlonK protocol that uniformizes the Verifier’s work for families of circuits. Specifically, a single fixed-cost “Universal Verifier” can check proofs for circuits of different: sizes, public input lengths, selector polynomials, copy constraints, and even different custom gate sets. UniPlonK therefore extends the universality of PlonK beyond the SRS; it enables a single “Universal Verifier Circuit” capable of verifying proofs from different PlonK circuits. The Universal Verifier’s marginal cost over the ordinary Plonk verifier is small: for circuits using only the vanilla Plonk gate, the Universal Verifier performs a number of additional field multiplications proportional to the logarithm of the maximum supported circuit size; it incurs no additional elliptic curve operations. For circuits using custom gates, the Universal Verifier incurs additional elliptic curve arithmetic only when verifying proofs from circuits that do not use all supported gate types. For circuits that use all supported gates, the Universal Verifier’s additional cost consists only of field multiplications proportional to the logarithm of the maximum supported circuit size, the number of custom gate types, and the number of witness variables used by these gates. In both settings (vanilla-only and custom gates) the marginal cost to the prover is a fixed-base MSM of size ℓ, the length of the public input vector.

Modern security systems depend fundamentally on the ability of users to authenticate their communications to other parties in a network. Unfortunately, cryptographic authentication can substantially undermine the privacy of users. One possible solution to this problem is to use privacy-preserving cryptographic authentication. These protocols allow users to authenticate their communications without revealing their identity to the verifier. In the non-interactive setting, the most common protocols include blind, ring, and group signatures, each of which has been the subject of enormous research in the security and cryptography literature. These primitives are now being deployed at scale in major applications, including Intel's SGX software attestation framework. The depth of the research literature and the prospect of large-scale deployment motivate us to systematize our understanding of the research in this area. This work provides an overview of these techniques, focusing on applications and efficiency.

The advent of quantum computers poses a serious challenge to the security of cloud infrastructures and services, as they can potentially break the existing public-key cryptosystems, such as Rivest–Shamir–Adleman (RSA) and Elliptic Curve Cryptography (ECC). Even though the gap between today’s quantum computers and the threats they pose to current public-key cryptography is large, the cloud landscape should act proactively and initiate the transition to the post-quantum era as early as possible. To comply with that, the U.S. government issued a National Security Memorandum in May 2022 that mandated federal agencies to migrate to post-quantum cryptosystems (PQC) by 2035. To ensure the long-term security of cloud computing, it is imperative to develop and deploy PQC resistant to quantum attacks. A promising class of post-quantum cryptosystems is based on lattice problems, which require polynomial arithmetic. In this paper, we propose and implement a scalable number-theoretic transform (NTT) architecture that significantly enhances the performance of polynomial multiplication. Our proposed design exploits multi-levels of parallelism to accelerate the NTT computation on reconfigurable hardware. We use the high-level synthesis (HLS) method to implement our design, which allows us to describe the NTT algorithm in a high-level language and automatically generate optimized hardware code. HLS facilitates rapid prototyping and enables us to explore different design spaces and trade-offs on the hardware platforms. Our experimental results show that our design achieves 11$\times$ speedup compared to the state-of-the-art requiring only 14 clock cycles for an NTT computation over a polynomial of degree 256. To demonstrate the applicability of our design, we also present a coprocessor architecture for Kyber, a key encapsulation mechanism (KEM) chosen by the NIST post-quantum standardization process, that utilizes our scalable NTT core.

The low-degree method postulates that no efficient algorithm outperforms low-degree polynomials in certain hypothesis-testing tasks. It has been used to understand computational indistinguishability in high-dimensional statistics. We explore the use of the low-degree method in the context of cryptography. To this end, we apply it in the design and analysis of a new public-key encryption scheme whose security is based on Goldreich's pseudorandom generator. The scheme is a combination of two proposals of Applebaum, Barak, and Wigderson, and inherits desirable features from both.

Topological Data Analysis (TDA) offers a suite of computational tools that provide quantified shape features in high dimensional data that can be used by modern statistical and predictive machine learning (ML) models. In particular, persistent homology (PH) takes in data (e.g., point clouds, images, time series) and derives compact representations of latent topological structures, known as persistence diagrams (PDs). Because PDs enjoy inherent noise tolerance, are interpretable and provide a solid basis for data analysis, and can be made compatible with the expansive set of well-established ML model architectures, PH has been widely adopted for model development including on sensitive data, such as genomic, cancer, sensor network, and financial data. Thus, TDA should be incorporated into secure end-to-end data analysis pipelines. In this paper, we take the first step to address this challenge and develop a version of the fundamental algorithm to compute PH on encrypted data using homomorphic encryption (HE).

In recent years, many digital signature scheme proposals have been built from the so-called MPC-in-the-head paradigm. This has shown to be an outstanding way to design efficient signatures with security based on hard problems. MinRank is an NP-complete problem extensively studied due to its applications to cryptanalysis since its introduction in 1999. However, only a few schemes base their security on its intractability, and their signature size is large compared with other proposals based on NP problems. This paper introduces the first MinRank-based digital signature scheme that uses the MPC-in-the-head, enabling it to achieve small signature sizes and running times. For NIST's category I parameter set, we obtain signatures of 6.5KB, which is competitive with the shortest proposals in the literature that are based on non-structured problems.

Lattice-based digital signature schemes following the hash-and-sign design paradigm of Gentry, Peikert and Vaikuntanathan (GPV) tend to offer an attractive level of efficiency, particularly when instantiated with structured compact trapdoors. In particular, NIST postquantum finalist Falcon is both quite fast for signing and verification and quite compact: NIST notes that it has the smallest bandwidth (as measured in combined size of public key and signature) of all round 2 digital signature candidates. Nevertheless, while Falcon--512, for instance, compares favorably to ECDSA--384 in terms of speed, its signatures are well over 10 times larger. For applications that store large number of signatures, or that require signatures to fit in prescribed packet sizes, this can be a critical limitation. In this paper, we explore several approaches to further improve the size of hash-and-sign lattice-based signatures, particularly instantiated over NTRU lattices like Falcon and its recent variant Mitaka. In particular, while GPV signatures are usually obtained by sampling lattice points according to some \emph{spherical} discrete Gaussian distribution, we show that it can be beneficial to sample instead according to a suitably chosen \emph{ellipsoidal} discrete Gaussian: this is because only half of the sampled Gaussian vector is actually output as the signature, while the other half is recovered during verification. Making the half that actually occurs in signatures shorter reduces signature size at essentially no security loss (in a suitable range of parameters). Similarly, we show that reducing the modulus $q$ with respect to which signatures are computed can improve signature size as well as verification key size almost ``for free''; this is particularly true for constructions like Falcon and Mitaka that do not make substantial use of NTT-based multiplication (and rely instead on transcendental FFT). Finally, we show that the Gaussian vectors in signatures can be represented in a more compact way with appropriate coding-theoretic techniques, improving signature size by an additional 7 to 14%. All in all, we manage to reduce the size of, e.g., Falcon signatures by 30--40% at the cost of only 4--6 bits of Core-SVP security.

Let $N=pq$ be the product of two balanced prime numbers $p$ and $q$. Murru and Saettone presented in 2017 an interesting RSA-like cryptosystem that uses the key equation $ed - k (p^2+p+1)(q^2+q+1) = 1$, instead of the classical RSA key equation $ed - k (p-1)(q-1) = 1$. The authors claimed that their scheme is immune to Wiener's continued fraction attack. Unfortunately, Nitaj \emph{et. al.} developed exactly such an attack. In this paper, we introduce a family of RSA-like encryption schemes that uses the key equation $ed - k [(p^n-1)(q^n-1)]/[(p-1)(q-1)] = 1$, where $n>1$ is an integer. Then, we show that regardless of the choice of $n$, there exists an attack based on continued fractions that recovers the secret exponent.

In this work, we introduce a new attack for the Loidreau scheme [PQCrypto 2017] and its more recent variant LowMS. This attack is based on a constrained linear system for which we provide two solving approaches: - The first one is an enumeration algorithm inspired from combinatorial attacks on the Rank Decoding (RD) Problem. While the attack technique remains very simple, it allows us to obtain the best known structural attack on the parameters of these two schemes. - The second one is to rewrite it as a bilinear system over Fq. Even if Gröbner basis techniques on this second system seem infeasible, we provide a detailed analysis of the first degree fall polynomials which arise when applying such algorithms.

In this work we introduce a new code-based signature scheme, called \textsf{FuLeeca}, based on the NP-hard problem of finding codewords of given Lee-weight. The scheme follows the Hash-and-Sign approach applied to quasi-cyclic codes. Similar approaches in the Hamming metric have suffered statistical attacks, which revealed the small support of the secret basis. Using the Lee metric, we are able to thwart such attacks. We use existing hardness results on the underlying problem and study adapted statistical attacks. We propose parameters for \textsf{FuLeeca}~and compare them to an extensive list of proposed post-quantum secure signature schemes including the ones already standardized by NIST. This comparison reveals that \textsf{FuLeeca}~is competitive. For example, for NIST category I, i.e., 160 bit of classical security, we obtain an average signature size of 1100 bytes and public key sizes of 1318 bytes. Comparing the total communication cost, i.e., the sum of the signature and public key size, we see that \textsf{FuLeeca} is only outperformed by Falcon while the other standardized schemes Dilithium and SPHINCS+ show larger communication costs than \textsf{FuLeeca}.

In this paper, we will show the hidden discrete logarithm problem(HDLP) and the generalized form of HDLP(GHDLP) over non-commutative associative algebras (FNAAs) can be reduced to discrete logarithm problem(DLP) in a finite field through analyzing the eigenvalues of the representation matrix. Through the analysis of computational complexity, we will show that HDLP and GHDLP is not are not good improvements of DLP.With all the instruments in hand, we will show how some schemes based on GHDLP can be broken. Thus we can conclude that, all ideas of constructing cryptographic schemes based on the two problem are of no practical significance.

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.

In a hybrid key establishment system, multiple independent key establishment schemes are combined in a manner that also combines their security properties. Such constructions can combine systems that are secure in different settings and achieve the combined security of all systems. For example, classical and post-quantum systems can be combined in order to secure communication against current threats as well as future quantum adversaries. This paper describes machine-checked proofs of security for a commonly-used hybrid key establishment system that concatenates the secrets produced by other key establishment systems. Practical interpretation of these results is also provided in order to guide the use of this system in applications and standards.

In recent history of fully homomorphic encryption, bootstrapping has been actively studied throughout many HE schemes. As bootstrapping is an essential process to transform somewhat homomorphic encryption schemes into fully homomorphic, enhancing its performance is one of the key factors of improving the utility of homomorphic encryption. In this paper, we propose an extended bootstrapping for TFHE, which we name it by EBS. One of the main drawback of TFHE bootstrapping was that the precision of bootstrapping is mainly decided by the polynomial dimension $N$. Thus if one wants to bootstrap with high precision, one must enlarge $N$, or take alternative method. Our EBS enables to use small $N$ for parameter selection, but to bootstrap in higher dimension to keep high precision. Moreover, it can be easily parallelized for faster computation. Also, the EBS can be easily adapted to other known variants of TFHE bootstrappings based on the original bootstrapping algorithm. We implement our EBS along with the full domain bootstrapping methods known ($\mathsf{FDFB}$, $\mathsf{TOTA}$, $\mathsf{Comp}$), and show how much our EBS can improve the precision for those bootstrapping methods. We provide experimental results and thorough analysis with our EBS, and show that EBS is capable of bootstrapping with high precision even with small $N$, thus small key size, and small complexity than selecting large $N$ by birth.

We present $\mathsf{Testudo}$, a new FFT-less SNARK with a near linear-time prover, constant-time verifier, constant-size proofs and a square-root-size universal setup. $\mathsf{Testudo}$ is based on a variant of Spartan~\cite{C:Setty20}—and hence does not require FFTs—as well as a new, fast multivariate polynomial commitment scheme (PCS) with a square-root-sized trusted setup that is derived from PST (TCC 2013) and IPPs (Asiacrypt 2021). To achieve constant-size SNARK proofs in $\mathsf{Testudo}$ we then combine our PCS openings proofs recursively with a Groth16 SNARK. We also evaluate our construction and its building blocks: to compute a PCS opening proof for a polynomial of size $2^{25}$, our new scheme opening procedure achieves a 110x speed-up compared to PST and 3x compared to Gemini (Eurocrypt 2022), since opening computations are heavily parallelizable and operate on smaller polynomials. Furthermore, a $\mathsf{Testudo}$ proof for a witness of size $2^{30} (\approx 1\,GB)$ requires a setup of size only $2^{15}$ ($\approx$ tens of kilobytes). Finally, we show that a $\mathsf{Testudo}$ variant for proving data-parallel computations is almost 10x faster at verifying $2^{10}$ Poseidon-based Merkle tree opening proofs than the regular version.

Fully Homomorphic Encryption over the Torus (TFHE) is a homomorphic encryption scheme which supports efficient Boolean operations over encrypted bits. TFHE has a unique feature in that the evaluation of each binary gate is followed by a bootstrapping procedure to refresh the noise of a ciphertext. In particular, this gate bootstrapping involves two algorithms called the blind rotation and key-switching. In this work, we introduce several optimization techniques for the TFHE bootstrapping. We first define a new key distribution, called the block binary distribution, where the secret key can be expressed as a concatenation of several vectors of Hamming weight at most one. We analyze the hardness of (Ring) LWE with a block binary secret and provide candidate parameter sets which are secure against the best-known attacks. Then, we use the block key structure to simplify the inner working of blind rotation and reduce its complexity. We also modify the RLWE key generation and the gadget decomposition method to improve the performance of the key-switching algorithm in terms of complexity and noise growth. Finally, we use the TFHE library to implement our algorithms and demonstrate their benchmarks. Our experimentation shows that the execution time of TFHE bootstrapping is reduced from 10.5ms down to 6.4ms under the same security level, and the size of the bootstrapping key decreases from 109MB to 60MB.

A famous reduction by Regev shows that random instances of the Learning With Errors (LWE) problem are asymptotically at least as hard as a worst-case lattice problem. As such, by assuming that standard lattice problems are hard to solve, the asymptotic security of cryptosystems based on the LWE problem is guaranteed. However, it has not been clear to which extent, if any, this reduction provides support for the security of present concrete parametrizations. In this work we therefore use Regev's reduction to parametrize a cryptosystem, providing a reference as to what parameters are required to actually claim security from this reduction. This requires us to account for the concrete performance of this reduction, allowing the first parametrization of a cryptosystem that is provably secure based only on a conservative hardness estimate for a standard lattice problem. Even though we attempt to optimize the reduction, our system still requires significantly larger parameters than typical LWE-based cryptosystems, highlighting the significant gap between parameters that are used in practice and those for which worst-case reductions actually are applicable.

The Fiat-Shamir with Aborts paradigm of Lyubashevsky has given rise to efficient lattice-based signature schemes. One popular implementation is Dilithium which is a finalist in an ongoing standardization process run by the NIST. Informally, it can be seen as a lattice analogue of the well-known discrete-logarithm-based Schnorr signature. An interesting research question is whether it is possible to combine several unrelated signatures, issued from different signing parties on different messages, into one single aggregated signature. Of course, its size should be significantly smaller than the trivial concatenation of all signatures. Ideally, the aggregation can be done offline by a third party, called public aggregation. Previous works have shown that it is possible to half-aggregate Schnorr signatures, but it was left unclear if the underlying techniques can be adapted to the lattice setting. In this work, we show that, indeed, we can use similar strategies to obtain a signature scheme allowing for public aggregation whose hardness is proven assuming the intractability of two well-studied problems on module lattices: The Module Learning With Errors problem (M-LWE) and the Module Short Integer Solution problem (M-SIS). Unfortunately, our scheme produces aggregated signatures that are larger than the trivial solution of concatenating. This is due to peculiarities that seem inherent to lattice-based cryptography. Its motivation is thus mainly pedagogical, as we explain the subtleties when designing lattice-based aggregate signatures that are supported by a proper security proof.

PASS Encrypt is a lattice-based public key encryption scheme introduced by Hoffstein and Silverman in 2015. The efficiency and algebraic properties of PASS Encrypt and of the underlying partial Vandermonde knapsack problem (PV-Knap) make them an attractive starting point for building efficient post-quantum cryptographic primitives. Recall that PV-Knap asks to recover a polynomial of small norm from a partial list of its Vandermonde transform. Unfortunately, the security foundations of PV-Knap-based encryption are not well understood, and in particular, no security proof for PASS Encrypt is known. In this work, we make progress in this direction. First, we present a modified version of PASS Encrypt with a security proof based on decision PV-Knap and a leaky variant of it, named the PASS problem. We next study an alternative approach to build encryption based on PV-Knap. To this end, we introduce the partial Vandermonde LWE problem (PV-LWE), which we show is computationally equivalent to PV-Knap. Following Regev's design for LWE-based encryption, we use PV-LWE to construct an efficient encryption scheme. Its security is based on PV-LWE and a hybrid variant of PV-Knap and Polynomial LWE. Finally, we give a refined analysis of the concrete security of both schemes against best known lattice attacks.

We address the problem of user fast revocation in the lattice based CP-ABE by extending the scheme originally introduced in [A ciphertext policy attribute-based encryption scheme without pairings. J. Zhang, Z. Zhang - ICISC 2011]. While a lot of work exists on the construction of revocable schemes for CP-ABE based on pairings, works based on lattices are not so common, and – to the best of our knowledge – we introduce the first server-aided revocation scheme in a lattice based CP-ABE scheme, hence providing post-quantum safety. In particular, we rely on semi-trusted "mediators" to provide a multi-step decryption capable of handling mediation without re-encryption. We comment on the scheme and its application and we provide performance experiments on a prototype implementation in the ABE spin-off library of Palisade to evaluate the overhead compared with the original scheme.

We present a new, simple candidate broadcast encryption scheme for $N$ users with parameter size poly$(\log N)$. We prove security of our scheme under a non-standard variant of the LWE assumption where the distinguisher additionally receives short Gaussian pre-images, while avoiding zeroizing attacks. This yields the first candidate optimal broadcast encryption that is plausibly post-quantum secure, and enjoys a security reduction to a simple assumption. As a secondary contribution, we present a candidate ciphertext-policy attribute-based encryption (CP-ABE) scheme for circuits of a-priori bounded polynomial depth where the parameter size is independent of the circuit size, and prove security under an additional non-standard assumption.

There are two competing approaches to bootstrap the FHEW fully homomorphic encryption scheme (Ducas and Micciancio, Eurocrypt 2015) and its variants: the original AP/FHEW method, which supports arbitrary secret key distributions, and the improved GINX/TFHE method, which uses much smaller evaluation keys, but is directly applicable only to binary secret keys, restricting the scheme's applicability. In this paper, we present a new bootstrapping procedure for FHEW-like encryption schemes that achieves the best features of both methods: support for arbitrary secret key distributions at no additional runtime costs, while using small evaluation keys. (Support for arbitrary secret keys is critical in a number of important applications, like threshold and some multi-key homomorphic encryption schemes.) As an added benefit, our new bootstrapping procedure results in smaller noise growth than both AP and GINX, regardless of the key distribution. Our improvements are both theoretically significant (offering asymptotic savings, up to a $O(\log n)$ multiplicative factor, either on the running time or public evaluation key size), and practically relevant. For example, for a concrete 128-bit target security level, we show how to decrease the evaluation key size of the best previously known scheme by more than 30%, while also slightly reducing the running time. We demonstrate the practicality of the proposed methods by building a prototype implementation within the PALISADE/OpenFHE open-source homomorphic encryption library. We provide optimized parameter sets and implementation results showing that the proposed algorithm has the best performance among all known FHEW bootstrapping methods in terms of runtime and key size. We illustrate the benefits of our method by sketching a simple construction of threshold homomorphic encryption based on FHEW.

This is the second update of this report. In this update, we partially solve Open problem 2 and completely solve Open problem 3 from the previous version. By doing this we address one modification of the Panny's attack done by Nils Langius. In the first update we introduced conditions for choosing the parameters that render the attacks (both classical and quantum algorithms attacks) proposed by Lorenz Panny in March 2023 on the first variant, inapplicable. For the classical attack, we prove that the discrete logarithms that he was basing his attack upon do not exist for the new parameters. For the quantum algorithm attacks where he proposed computing a basis of a three-dimensional lattice, as proposed in Kitaev's generalization of Shor's quantum algorithm, we prove that for our transformation, the rank of that lattice (the Abelian Stabiliser in Kitaev's terminology) has a rank one, which makes the Kitaev's quantum algorithm inapplicable. In this paper we construct algebraic structures where rising to the non-associative power indices is no longer tied with the Discrete Logarithm Problem but with a variant of a problem that has been analysed in the last two decades and does not have a quantum polynomial algorithm that solves it. The problem is called Exponential Congruences Problem (ECP). By this, \emph{we disprove} the claims presented in the ePrint report 2021/583 titled "Entropoids: Groups in Disguise" by Lorenz Panny that \emph{"all instantiations of the entropoid framework should be breakable in polynomial time on a quantum computer."} Additionally, we construct an Arithmetic for power indices and propose generic recipe guidelines that we call "Entropic-Lift" for transforming some of the existing classical cryptographic schemes that depend on the hardness of Discrete Logarithm Problem to post-quantum cryptographic schemes that will base their security on the hardness of the Entropoid variant of the Exponential Congruences Problem (EECP). As concrete examples, we show how to transform the classical Diffie-Hellman key exchange, DSA and Schnorr signature schemes. We also post several open problems (two of them now are solved) in relation to EECP and the "Entropic-Lift" transformation.

Key mismatch attacks resilience is a great concern for KEMs in the NIST PQC standardization process. In key mismatch attacks, the adversary aims to recover the reused key by sending special form of ciphertexts to the target party and observing whether the shared key matches his guesses or not. In this paper, we propose pairwise-parallel key mismatch attacks on Kyber and other lattice-based KEMs. The strategy is to recover partial information about multiple secret key coefficient-pairs in a parallel way per query. We realize the required multi-value key mismatch oracle in a simple key exchange scenario and experimentally validate our proposed attacks. Our attacks greatly reduce the number of queries required to recover the full secret key. Specifically, compared with state-of-the-art key mismatch attacks on CPA-secure Kyber, our attacks reduce the number of queries by 95% with computational complexity $2^{32}$. Then we employ the post-processing with lattice reduction to further minimize the number of queries. The results show we only need 78 queries to recover the full secret key with a lattice reduction cost of $2^{32}$. Moreover, our proposed pairwise-parallel attack method can be directly applied to enhance the PC oracle-based SCA against CCA-secure Kyber, reducing the number of queries/traces by 16.67%.

The major objective of this paper is to present a theoretical model for an algorithm that has not been previously described in the literature, capable of generating a secret key through the transmission of data over a public channel. We explain how the method creates a shared secret key by attaining commutativity through the multiplication of the modular exponentiation of a minimum of two bases and an equal number of private exponents for each party involved in the exchange. In addition, we explore the relationship between CMME and the traditional Diffie-Hellman scheme. We just briefly discuss the algorithm's security, opting to leave the essential investigation to cryptanalysts, while we elucidate on the algorithm's mechanism by illustrating some cases.

A multi-signature scheme allows multiple signers to jointly sign a common message. In recent years, two lattice-based two-round multi-signature schemes based on Dilithium-G were proposed: DOTT by Damgård, Orlandi, Takahashi, and Tibouchi (PKC'21) and Musig-L by Boschini, Takahashi, and Tibouchi (CRYPTO'22). In this work, we propose a new lattice-based two-round multi-signature scheme called DualMS. Compared to DOTT, DualMS is likely to significantly reduce signature size, since it replaces an opening to a homomorphic trapdoor commitment with a Dilithium-G response in the signature. Compared to Musig-L, concrete parameters show that DualMS has smaller public keys, signatures, and lower communication, while the first round cannot be preprocessed offline as in Musig-L. The main reason behind such improvements is a trapdoor-free "dual signing simulation" of our scheme. Signature simulation of DualMS is virtually the same as the normal signing procedure and does not use lattice trapdoors like DOTT and Musig-L.

In this paper we study non-trivial self-pairings with cyclic domains that are compatible with isogenies between elliptic curves oriented by an imaginary quadratic order $\mathcal{O}$. We prove that the order $m$ of such a self-pairing necessarily satisfies $m \mid \Delta_\mathcal{O}$ (and even $2m \mid \Delta_\mathcal{O} $ if $4 \mid \Delta_\mathcal{O}$ and $4m \mid \Delta_\mathcal{O}$ if $8 \mid \Delta_\mathcal{O}$) and is not a multiple of the field characteristic. Conversely, for each $m$ satisfying these necessary conditions, we construct a family of non-trivial cyclic self-pairings of order $m$ that are compatible with oriented isogenies, based on generalized Weil and Tate pairings. As an application, we identify weak instances of class group actions on elliptic curves assuming the degree of the secret isogeny is known. More in detail, we show that if $m^2 \mid \Delta_\mathcal{O}$ for some prime power $m$ then given two primitively $\mathcal{O}$-oriented elliptic curves $(E, \iota)$ and $(E',\iota') = [\mathfrak{a}] (E,\iota)$ connected by an unknown invertible ideal $\mathfrak{a} \subseteq \mathcal{O}$, we can recover $\mathfrak{a}$ essentially at the cost of a discrete logarithm computation in a group of order $m^2$, assuming the norm of $\mathfrak{a}$ is given and is smaller than $m^2$. We give concrete instances, involving ordinary elliptic curves over finite fields, where this turns into a polynomial time attack. Finally, we show that these self-pairings simplify known results on the decisional Diffie-Hellman problem for class group actions on oriented elliptic curves.

Hofheinz et al. (TCC 2017) proposed several key encapsulation mechanism (KEM) variants of Fujisaki-Okamoto (\textsf{FO}) transformation, including $\textsf{FO}^{\slashed{\bot}}$, $\textsf{FO}_m^{\slashed{\bot}}$, $\textsf{QFO}_m^{\slashed{\bot}}$, $\textsf{FO}^{\bot}$, $\textsf{FO}_m^\bot$ and $\textsf{QFO}_m^\bot$, and they are widely used in the post-quantum cryptography standardization launched by NIST. These transformations are divided into two types, the implicit and explicit rejection type, including $\{\textsf{FO}^{\slashed{\bot}}, \textsf{FO}_m^{\slashed{\bot}}, \textsf{QFO}_m^{\slashed{\bot}}\}$ and $\textsf{FO}^{\bot}, \textsf{FO}_m^\bot, \textsf{QFO}_m^\bot$, respectively. The decapsulation algorithm of the implicit (resp. explicit) rejection type returns a pseudorandom value (resp. an abort symbol $\bot$) for an invalid ciphertext. For the implicit rejection type, the \textsf{IND-CCA} security reduction of $\textsf{FO}^{\slashed{\bot}}$ in the quantum random oracle model (QROM) can avoid the quadratic security loss, as shown by Kuchta et al. (EUROCRYPT 2020). However, for the explicit rejection type, the best known \textsf{IND-CCA} security reduction in the QROM presented by Hövelmanns et al. (ASIACRYPT 2022) for $\textsf{FO}_m^\bot$ still suffers from a quadratic security loss. Moreover, it is not clear until now whether the implicit rejection type is more secure than the explicit rejection type. In this paper, a QROM security reduction of $\textsf{FO}_m^\bot$ without incurring a quadratic security loss is provided. Furthermore, our reduction achieves \textsf{IND-qCCA} security, which is stronger than the \textsf{IND-CCA} security. To achieve our result, two steps are taken: The first step is to prove that the \textsf{IND-qCCA} security of $\textsf{FO}_m^\bot$ can be tightly reduced to the \textsf{IND-CPA} security of $\textsf{FO}_m^\bot$ by using the online extraction technique proposed by Don et al. (EUROCRYPT 2022). The second step is to prove that the \textsf{IND-CPA} security of $\textsf{FO}_m^\bot$ can be reduced to the \textsf{IND-CPA} security of the underlying public key encryption (PKE) scheme without incurring quadratic security loss by using the Measure-Rewind-Measure One-Way to Hiding Lemma (EUROCRYPT 2020). In addition, we prove that (at least from a theoretic point of view), security is independent of whether the rejection type is explicit ($\textsf{FO}_m^\bot$) or implicit ($\textsf{FO}_m^{\slashed{\bot}}$) if the underlying PKE scheme is weakly $\gamma$-spread.

We construct the first tightly secure authenticated key exchange (AKE) protocol from lattices. Known tight constructions are all based on Diffie-Hellman-like assumptions. Thus, our protocol is the first construction with tight security from a post-quantum assumption. Our AKE protocol is constructed tightly from a new security notion for key encapsulation mechanisms (KEMs), called one-way security against checkable chosen-ciphertext attacks (OW- ChCCA). We show how an OW-ChCCA secure KEM can be tightly constructed based on the Learning With Errors assumption, leading to the desired AKE protocol. To show the usefulness of OW-ChCCA security beyond AKE, we use it to construct the first tightly bilateral selective-opening (BiSO) secure PKE. BiSO security is a stronger selective-opening notion proposed by Lai et al. (ASIACRYPT 2021).

Hash-based signatures offer a conservative alternative to post-quantum signatures with arguably better-understood security than other post-quantum candidates. As a core building block of hash-based signatures, the efficiency of one-time signature (OTS) largely dominates that of hash-based signatures. The WOTS$^{+}$ signature scheme (Africacrypt 2013) is the current state-of-the-art OTS adopted by the signature schemes standardized by NIST---XMSS, LMS and SPHINCS$^+$. A natural question is whether there is (and how much) room left for improving one-time signatures (and thus standard hash-based signatures). In this paper, we show that WOTS$^{+}$ one-time signature, when adopting the constant-sum encoding scheme (Bos and Chaum, Crypto 1992), is size-optimal not only under Winternitz's OTS framework, but also among all tree-based OTS designs. Moreover, we point out a flaw in the DAG-based OTS design previously shown to be size-optimal at Asiacrypt 1996, which makes the constant-sum WOTS$^{+}$ the most size-efficient OTS to the best of our knowledge. Finally, we evaluate the performance of constant-sum WOTS$^{+}$ integrated into the SPHINCS$^+$ (CCS 2019) and XMSS (PQC 2011) signature schemes which exhibit certain degrees of improvement in both signing time and signature size.

Public-key encryption with keyword search (PEKS) does not provide trapdoor privacy, i.e., keyword information is leaked through trapdoors. To prevent this information leakage, public key authenticated encryption with keyword search (PAEKS) has been proposed, where a sender's secret key is required for encryption, and a trapdoor is associated with not only a keyword but also the sender. Liu et al. (ASIACCS 2022) proposed a generic construction of PAEKS based on word-independent smooth projective hash functions (SPHFs) and PEKS. In this paper, we propose a new generic construction of PAEKS. The basic construction methodology is the same as that of the Liu et al. construction, where each keyword is converted into an extended keyword using SPHFs, and PEKS is used for extended keywords. Nevertheless, our construction is more efficient than Liu et al.'s in the sense that we only use one SPHF, but Liu et al. used two SPHFs. In addition, for consistency we considered a security model that is stronger than Liu et al.'s. Briefly, Liu et al. considered only keywords even though a trapdoor is associated with not only a keyword but also a sender. Thus, a trapdoor associated with a sender should not work against ciphertexts generated by the secret key of another sender, even if the same keyword is associated. Our consistency definition considers a multi-sender setting and captures this case. In addition, for indistinguishability against chosen keyword attack (IND-CKA) and indistinguishability against inside keyword guessing attack (IND-IKGA), we use a stronger security model defined by Qin et al. (ProvSec 2021), where an adversary is allowed to query challenge keywords to the encryption and trapdoor oracles. We also highlight several issues associated with the Liu et al. construction in terms of hash functions, e.g., their construction does not satisfy the consistency that they claimed to hold.

This paper presents a novel e-voting scheme that combines Group Identity-based Identification (GIBI) with Homomorphic Encryption (HE) based on the discrete logarithmic assumption. The proposed scheme uses the Schnorr-like GIBI scheme for voter identification and authorization using Zero-Knowledge (ZK) proof to ensure the anonymity and eligibility of voters. The use of Distributed ElGamal (DE) provides fairness and receipt-freeness, while the use of partial shares for decryption enables individual and universal verifiability without the need for a central authority. Voters can maintain uncoerability by encrypting their votes and casting ballots based on their own choice. The proposed scheme is secure under various scenarios and robust in the Random Oracle (RO) model. The GIBI-HE scheme offers a promising solution for e-voting, providing a sustainable and accessible environment for voters while supports unreusability of votes and protecting privacy of voter.

We give a quantum reduction from finding short codewords in a random linear code to decoding for the Hamming metric. This is the first time such a reduction (classical or quantum) has been obtained. Our reduction adapts to linear codes Stehlé-Steinfield-Tanaka-Xagawa’ re-interpretation of Regev's quantum reduction from finding short lattice vectors to solving the Closest Vector Problem. The Hamming metric is a much coarser metric than the Euclidean metric and this adaptation has needed several new ingredients to make it work. For instance, in order to have a meaningful reduction it is necessary in the Hamming metric to choose a very large decoding radius and this needs in many cases to go beyond the radius where decoding is always unique. Another crucial step for the analysis of the reduction is the choice of the errors that are being fed to the decoding algorithm. For lattices, errors are usually sampled according to a Gaussian distribution. However, it turns out that the Bernoulli distribution (the analogue for codes of the Gaussian) is too much spread out and cannot be used, as such, for the reduction with codes. This problem was solved by using instead a truncated Bernoulli distribution.

We present a novel code-based digital signature scheme, called Enhanced pqsigRM for post-quantum cryptography (PQC). This scheme is based on modified Reed–Muller (RM) codes, which modified RM codes with several security problems. Enhanced pqsigRM is a strengthened version of pqsigRM, which was submitted to NIST PQC standardization in round 1. The proposed scheme has the advantage of short signature size, fast verification cycles. For 128 bits of classical security, the signature size of the proposed scheme is 1032 bytes, which corresponds to 0.42 times that of Crystals-Dilithium, and the number of median verification cycles is 235,656, which is smaller than that of Crystals-Dilithium. Also, we use public codes, called modified RM codes, that are more difficult to distinguish from random codes. We use (U,U + V )-codes with high-dimensional hull to make these. Using modified RM codes, the proposed signature scheme resists various known attacks on RM-code-based cryptography. The proposed decoder samples from coset elements with small Hamming weight for any given syndrome and efficiently finds such elements.

As part of the responses to the ongoing ``crypto wars,'' the notion of {\em Anamorphic Encryption} was put forth [Persiano-Phan-Yung Eurocrypt '22]. The notion allows private communication in spite of a dictator who (in violation of the usual normative conditions under which Cryptography is developed) is engaged in an extreme form of surveillance and/or censorship, where it asks for all private keys and knows and may even dictate all messages. The original work pointed out efficient ways to use two known schemes in the anamorphic mode, bypassing the draconian censorship and hiding information from the all-powerful dictator. A question left open was whether these examples are outlier results or whether anamorphic mode is pervasive in existing systems. Here we answer the above question: we develop new techniques, expand the notion, and show that the notion of Anamorphic Cryptography is, in fact, very much prevalent. We first refine the notion of Anamorphic Encryption with respect to the nature of covert communication. Specifically, we distinguish {\em Single-Receiver Encryption} for many to one communication, and {\em Multiple-Receiver Encryption} for many to many communication within the group of conspiring (against the dictator) users. We then show that Anamorphic Encryption can be embedded in the randomness used in the encryption, and give families of constructions that can be applied to numerous ciphers. In total the families cover classical encryption schemes, some of which in actual use (RSA-OAEP, Pailler, Goldwasser-Micali, ElGamal schemes, Cramer-Shoup, and Smooth Projective Hash based systems). Among our examples is an anamorphic channel with much higher capacity than the regular channel. In sum, the work shows the very large extent of the potential futility of control and censorship over the use of strong encryption by the dictator (typical for and even stronger than governments engaging in the ongoing ``crypto-wars''): While such limitations obviously hurt utility which encryption typically brings to safety in computing systems, they essentially, are not helping the dictator. The actual implications of what we show here and what does it mean in practice require further policy and legal analyses and perspectives.

Revocable identity-based encryption (RIBE) is an extension of identity-based encryption (IBE) and it supports efficient revocation of private keys. In the past, many efficient RIBE schemes have been proposed, but research on efficiently delegating the generation of update keys to a cloud server is somewhat insufficient. In this paper, we newly introduce the concept of delegated RIBE (DRIBE) that can delegate the generation of update keys to the semi-trusted cloud server and define the security models of DRIBE. Next, we propose a DRIBE scheme by generically combining a hierarchical IBE (HIBE) scheme, an identity-based broadcast encryption (IBBE) scheme, and a collision-resistant hash function. In addition, we propose a DRIBE-INC scheme that generates an occasional base update key and a periodic incremental update key to reduce the size of the update key in our DRIBE scheme.

The Fujisaki-Okamoto (\textsf{FO}) transformation (CRYPTO 1999 and Journal of Cryptology 2013) and its KEM variants (TCC 2017) are used to construct \textsf{IND-CCA}-secure PKE or KEM schemes in the random oracle model (ROM). In the post-quantum setting, the ROM is extended to the quantum random oracle model (QROM), and the \textsf{IND-CCA} security of \textsf{FO} transformation and its KEM variants in the QROM has been extensively analyzed. Grubbs et al. (EUROCRYPTO 2021) and Xagawa (EUROCRYPTO 2022) then focused on security properties other than \textsf{IND-CCA} security, such as the anonymity aganist chosen-ciphertext attacks (\textsf{ANO-CCA}) of \textsf{FO} transformation in the QROM. Beyond the post-quantum setting, Boneh and Zhandry (CRYPTO 2013) considered quantum adversaries that can perform the quantum chosen-ciphertext attacks (\textsf{qCCA}). However, to the best of our knowledge, there are few results on the \textsf{IND-qCCA} or \textsf{ANO-qCCA} security of \textsf{FO} transformation and its KEM variants in the QROM. In this paper, we define a class of security games called the oracle-hiding game, and provide a lifting theorem for it. This theorem lifts the security reduction of oracle-hiding games in the ROM to that in the QROM. With this theorem, we prove the \textsf{IND-qCCA} and \textsf{ANO-qCCA} security of transformation $\textsf{FO}^{\slashed{\bot}}$, $\textsf{FO}^{\bot}$, $\textsf{FO}_m^{\slashed{\bot}}$ and $\textsf{FO}_m^\bot$, which are KEM variants of \textsf{FO}, in the QROM. Moreover, we prove the \textsf{ANO-qCCA} security of the hybrid PKE schemes built via the KEM-DEM paradigm, where the underlying KEM schemes are obtained by $\textsf{FO}^{\slashed{\bot}}$, $\textsf{FO}^{\bot}$, $\textsf{FO}_m^{\slashed{\bot}}$ and $\textsf{FO}_m^\bot$. Notably, for those hybrid PKE schemes, our security reduction shows that their anonymity is independent of the security of their underlying DEM schemes. Hence, our result simplifies the anonymity analysis of the hybrid PKE schemes that obtained from the \textsf{FO} transformation.

We introduce a new primitive called the asymmetric trapdoor pseudorandom generator (ATPRG), which belongs to pseudorandom generators with two additional trapdoors (a public trapdoor and a secret trapdoor) or backdoor pseudorandom generators with an additional trapdoor (a secret trapdoor). Specifically, ATPRG can only generate public pseudorandom numbers $pr_1,\dots,pr_N$ for the users having no knowledge of the public trapdoor and the secret trapdoor; so this function is the same as pseudorandom generators. However, the users having the public trapdoor can use any public pseudorandom number $pr_i$ to recover the whole $pr$ sequence; so this function is the same as backdoor pseudorandom generators. Further, the users having the secret trapdoor can use $pr$ sequence to generate a sequence $sr_1,\dots,sr_N$ of the secret pseudorandom numbers. ATPRG can help design more space-efficient protocols where data/input/message should respect a predefined (unchangeable) order to be correctly processed in a computation or malleable cryptographic system. As for applications of ATPRG, we construct the first homomorphic signature scheme (in the standard model) whose public key size is only $O(T)$ that is independent of the dataset size. As a comparison, the shortest size of the existing public key is $O(\sqrt{N}+\sqrt{T})$, proposed by Catalano et al. (CRYPTO'15), where $N$ is the dataset size and $T$ is the dimension of the message. In other words, we provide the first homomorphic signature scheme with $O(1)$-sized public keys for the one-dimension messages.

We provide identity-based signature (IBS) schemes with tight security against adaptive adversaries, in the (classical or quantum) random oracle model (ROM or QROM), in both unstructured and structured lattices, based on the SIS or RSIS assumption. These signatures are short (of size independent of the message length). Our schemes build upon a work from Pan and Wagner (PQCrypto’21) and improve on it in several ways. First, we prove their transformation from non-adaptive to adaptive IBS in the QROM. Then, we simplify the parameters used and give concrete values. Finally, we simplify the signature scheme by using a non-homogeneous relation, which helps us reduce the size of the signature and get rid of one costly trapdoor delegation. On the whole, we get better security bounds, shorter signatures and faster algorithms.

A recent area of interest in cryptography is recursive composition of proof systems. One of the approaches to make recursive composition efficient involves cycles of pairing-friendly elliptic curves of prime order. However, known constructions have very low embedding degrees. This entails large parameter sizes, which makes the overall system inefficient. In this paper, we explore $2$-cycles composed of curves from families parameterized by polynomials, and show that such cycles do not exist unless a strong condition holds. As a consequence, we prove that no $2$-cycles can arise from the known families, except for those cycles already known. Additionally, we show some general properties about cycles, and provide a detailed computation on the density of pairing-friendly cycles among all cycles.

Deniable encryption (Canetti et al. CRYPTO ’97) is an intriguing primitive, which provides security guarantee against coercion by allowing a sender to convincingly open the ciphertext into a fake message. Despite the notable result by Sahai and Waters STOC ’14 and other efforts in functionality extension, all the deniable public key encryption (DPKE) schemes suffer from intolerable overhead due to the heavy building blocks, e.g., translucent sets or indistinguishability obfuscation. Besides, none of them considers the possible damage from leakage in the real world, obstructing these protocols from practical use. To fill the gap, in this work we first present a simple and generic approach of sender-DPKE from ciphertext-simulatable encryption, which can be instantiated with nearly all the common PKE schemes. The core of this design is a newly-designed framework for flipping a bit-string that offers inverse polynomial distinguishability. Then we theoretically expound and experimentally show how classic side-channel attacks (timing or simple power attacks), can help the coercer to break deniability, along with feasible countermeasures.

In this short note we give another direct proof for the variant of the FO transform used by Kyber in the QROM. At PKC'23 Maram & Xagawa gave the first direct proof which does not require the indirection via FO with explicit rejection, thereby avoiding either a non-tight bound, or the necessity to analyze the failure probability in a new setting. However, on the downside their proof produces a bound that incurs an additive collision bound term. We explore a different approach for a direct proof, which results in a simpler argument closer to prior proofs, but a slightly worse bound.

We suggest a small change to the Dilithium signature scheme, that allows one to reuse computations between rejected nonces, for a speed-up in signing time. The modification is based on the idea that, after rejecting on a too large $\|\mathbf{r}_0\|_\infty$, not all elements of the nonce $\mathbf{y}$ are spent. We swap the order of the checks; and if this $\mathbf{r}_0$-check fails, we only need to resample $y_1$. We provide a proof that shows that the modification does not affect the security of the scheme. We present measurements of the performance of the modified scheme on AVX2, Cortex M4, and Cortex M3, which show a speed-up ranging from 11% for Dilithium2 on M3 to 22% for Dilithium3 on AVX2.

Algebraic Constructions of Extremal Graph Theory were efficiently used for the construction of Low Density Parity Check Codes for satellite communication, constructions of stream ciphers and Postquantum Protocols of Noncommutative cryptography and corresponding El Gamal type cryptosystems. We shortly observe some results in these applications and present idea of the usage of algebraic graphs for the development of Multivariate Public Keys (MPK). Some MPK schemes are presented at theoretical level, implementation of one of them is discussed.

We introduce large groups of quadratic transformations of a vector space over the finite fields defined via symbolic computations with the usage of algebraic constructions of Extremal Graph Theory. They can serve as platforms for the protocols of Noncommutative Cryptography with security based on the complexity of word decomposition problem in noncommutative polynomial transformation group. The modifications of these symbolic computations in the case of large fields of characteristic two allow us to define quadratic bijective multivariate public keys such that the inverses of public maps has a large polynomial degree. Another family of public keys is defined over arbitrary commutative ring with unity. We suggest the usage of constructed protocols for the private delivery of quadratic encryption maps instead of the public usage of these transformations, i.e. the idea of temporal multivariate rules with their periodical change.

With the increased use of data and communication through the internet and the abundant misuse of personal data by many organizations, people are more sensitive about their privacy. Privacy-preserving computation is becoming increasingly important in this era. Functional encryption allows a user to evaluate a function on encrypted data without revealing sensitive information. Most implementations of functional encryption schemes are too time-consuming for practical use. Mera et al. first proposed an inner product functional encryption scheme based on ring learning with errors to improve efficiency. In this work, we optimize the implementation of their work and propose a fast inner product functional encryption library. Specifically, we identify the main performance bottleneck, which is the number theoretic transformation based polynomial multiplication used in the scheme. We also identify the micro and macro level parallel components of the scheme and propose novel techniques to improve the efficiency using $\textit{open multi-processing}$ and $\textit{advanced vector extensions 2}$ vector processor. Compared to the original implementation, our optimization methods translate to $89.72\%$, $83.06\%$, $59.30\%$, and $53.80\%$ improvements in the $\textbf{Setup}$, $\textbf{Encrypt}$, $\textbf{KeyGen}$, and $\textbf{Decrypt}$ operations respectively, in the scheme for standard security level. Designing privacy-preserving applications using functional encryption is ongoing research. Therefore, as an additional contribution to this work, we design a privacy-preserving biometric authentication scheme using inner product functional encryption primitives.

Lattice gadgets and the associated algorithms are the essential building blocks of lattice-based cryptography. In the past decade, they have been applied to build versatile and powerful cryptosystems. However, the practical optimizations and designs of gadget-based schemes generally lag their theoretical constructions. For example, the gadget-based signatures have elegant design and capability of extending to more advanced primitives, but they are far less efficient than other lattice-based signatures. This work aims to improve the practicality of gadget-based cryptosystems, with a focus on hash-and-sign signatures. To this end, we develop a compact gadget framework in which the used gadget is a square matrix instead of the short and fat one used in previous constructions. To work with this compact gadget, we devise a specialized gadget sampler, called semi-random sampler, to compute the approximate preimage. It first deterministically computes the error and then randomly samples the preimage. We show that for uniformly random targets, the preimage and error distributions are simulatable without knowing the trapdoor. This ensures the security of the signature applications. Compared to the Gaussian-distributed errors in previous algorithms, the deterministic errors have a smaller size, which lead to a substantial gain in security and enables a practically working instantiation. As the applications, we present two practically efficient gadget-based signature schemes based on NTRU and Ring-LWE respectively. The NTRU-based scheme offers comparable efficiency to Falcon and Mitaka and a simple implementation without the need of generating the NTRU trapdoor. The LWE-based scheme also achieves a desirable overall performance. It not only greatly outperforms the state-of-the-art LWE-based hash-and-sign signatures, but also has an even smaller size than the LWE-based Fiat-Shamir signature scheme Dilithium. These results fill the long-term gap in practical gadget-based signatures.

The present work builds on previous investigations of the authors (and their collaborators) regarding bridges, a certain type of morphisms between encryption schemes, making a step forward in developing a (category theory) language for studying relations between encryption schemes. Here we analyse the conditions under which bridges can be performed sequentially, formalizing the notion of composability. One of our results gives a sufficient condition for a pair of bridges to be composable. We illustrate that composing two bridges, each independently satisfying a previously established IND-CPA security definition, can actually lead to an insecure bridge. Our main result gives a sufficient condition that a pair of secure composable bridges should satisfy in order for their composition to be a secure bridge. We also introduce the concept of a complete bridge and show that it is connected to the notion of Fully composable Homomorphic Encryption (FcHE), recently considered by Micciancio. Moreover, we show that a result of Micciancio which gives a construction of FcHE schemes can be phrased in the language of complete bridges, where his insights can be formalised in a greater generality.

The hard mathematical problems that assure the security of our current public-key cryptography (RSA, ECC) are broken if and when a quantum computer appears rendering them ineffective for use in the quantum era. Lattice based cryptography is a novel approach to public key cryptography, of which the mathematical investigation (so far) resists attacks from quantum computers. By choosing a module learning with errors (MLWE) algorithm as the next standard, National Institute of Standard \& Technology (NIST) follows this approach. The multiplication of polynomials is the central bottleneck in the computation of lattice based cryptography. Because public key cryptography is mostly used to establish common secret keys, focus is on compact area, power and energy budget and to a lesser extent on throughput or latency. While most other work focuses on optimizing number theoretic transform (NTT) based multiplications, in this paper we highly optimize a Toom-Cook based multiplier. We demonstrate that a memory-efficient striding Toom-Cook with lazy interpolation, results in a highly compact, low power implementation, which on top enables a very regular memory access scheme. To demonstrate the efficiency, we integrate this multiplier into a Saber post-quantum accelerator, one of the four NIST finalists. Algorithmic innovation to reduce active memory, timely clock gating and shift-add multiplier has helped to achieve 38\% less power than state-of-the art PQC core, 4 $\times$ less memory, 36.8\% reduction in multiplier energy and 118$\times$ reduction in active power with respect to state-of-the-art Saber accelerator (not silicon verified). This accelerator consumes $0.158mm^2$ active area which is lowest reported till date despite process disadvantages of the state-of-the-art designs.

In this paper, we prove the quantum security of the signature scheme HAWK, proposed by Ducas, Postlethwaite, Pulles and van Woerden (ASIACRYPT 2022). More precisely, we reduce its strong unforgeability in the quantum random oracle model (QROM) to the hardness of the one-more SVP problem, which is the computational problem on which also the classical security analysis of HAWK relies. Our security proof deals with the quantum aspects in a rather black-box way, making it accessible also to non-quantum-experts.

The key generation of the lattice-based key-encapsulation mechanism CRYSTALS-Kyber (or short, just Kyber) involves a rejection-sampling routine to produce coefficients modulo $q=3329$ that look uniformly random. The input to this rejection sampling is output of the SHAKE-128 extendable output function (XOF). If this XOF is modelled as a random oracle with infinite output length, it is easy to see that Kyber terminates with probability 1; also, in this model, for any upper bound on the running time, the probability of termination is strictly smaller than 1. In this short note we show that an (unconditional) upper bound for the running time for Kyber exists. Computing a tight upper bound, however, is (likely to be) infeasible. We remark that the result has no real practical value, except that it may be useful for computer-assisted reasoning about Kyber using tools that require a simple proof of termination.

An accountable subgroup multi-signature is a kind of multi-signature scheme in which any subgroup $\mathcal{S}$ of a group $\mathcal{G}$ of potential signers jointly sign a message $m$, ensuring that each member of $\mathcal{S}$ is accountable for the resulting signature. In this paper, we propose three novel pairing-based accountable subgroup multi-signature (ASM) schemes, which are secure against existential forgery under chosen-message attacks and computational co-Diffie-Hellman assumption. In the first one, we use Feldman’s verifiable secret sharing scheme as an implicit authentication and proof-of-possession for setting up group $\mathcal{G}$. In the second one, the members participating in authentication are decided by the subgroup. In the third one, we consider a designated combiner managing the authentication process. All schemes we propose here require fewer computations in the signature generation, signature aggregation, and verification phases than the pairing-based ASM scheme proposed by Boneh, Drijvers, and Neven. Moreover, our first and third ones solve the open problem of constructing an ASM scheme in which the subgroup $\mathcal{S}$ of signers is unknown before the signature generation. Besides, we give a method of eliminating the combiner in case of knowing the subgroup of signers $\mathcal{S}$ in advance. Further, we extend our proposed schemes to aggregated versions. For $N$ accountable subgroup multi-signatures, aggregated versions of our proposed schemes output an aggregated signature with the size of a single group ($\mathbb{G}_1$) element and require $N + 1$ pairings in aggregated signature verification. In contrast, the partially aggregated ASM scheme of Boneh, Drijvers, and Neven gives an aggregated signature with the size of $N + 1$ group elements and requires $2N + 1$ pairings in aggregated signature verification.

We present an efficient key recovery attack on the Supersingular Isogeny Diffie-Hellman protocol (SIDH). The attack is based on Kani's "reducibility criterion" for isogenies from products of elliptic curves and strongly relies on the torsion point images that Alice and Bob exchange during the protocol. If we assume knowledge of the endomorphism ring of the starting curve then the classical running time is polynomial in the input size (heuristically), apart from the factorization of a small number of integers that only depend on the system parameters. The attack is particularly fast and easy to implement if one of the parties uses 2-isogenies and the starting curve comes equipped with a non-scalar endomorphism of very small degree; this is the case for SIKE, the instantiation of SIDH that recently advanced to the fourth round of NIST's standardization effort for post-quantum cryptography. Our Magma implementation breaks SIKEp434, which aims at security level 1, in about ten minutes on a single core.

The parametrization of $(3,3)$-isogenies by Bruin, Flynn and Testa requires over 37.500 multiplications if one wants to evaluate a single isogeny in a point. We simplify their formulae and reduce the amount of required multiplications by 94%. Further we deduce explicit formulae for evaluating $(3,3)$-splitting and gluing maps in the framework of the parametrization by Bröker, Howe, Lauter and Stevenhagen. We provide implementations to compute $(3^n,3^n)$-isogenies between principally polarized abelian surfaces with a focus on cryptographic application. Our implementation can retrieve Alice's secret isogeny in 11 seconds for the SIKEp751 parameters, which were aimed at NIST level 5 security.

We show that the soundness proof for the De Feo-Jao-Plut identification scheme (the basis for supersingular isogeny Diffie--Hellman (SIDH) signatures) contains an invalid assumption, and we provide a counterexample for this assumption---thus showing the proof of soundness is invalid. As this proof was repeated in a number of works by various authors, multiple pieces of literature are affected by this result. Due to the importance of being able to prove knowledge of an SIDH key (for example, to prevent adaptive attacks), soundness is a vital property. Surprisingly, the problem of proving knowledge of a specific isogeny turns out to be considerably more difficult than was perhaps anticipated. The main results of this paper are a sigma protocol to prove knowledge of a walk of specified length in a supersingular isogeny graph, and a second one to additionally prove that the isogeny maps some torsion points to some other torsion points (as seen in SIDH public keys). Our scheme also avoids the SIDH identification scheme soundness issue raised by Ghantous, Pintore and Veroni. In particular, our protocol provides a non-interactive way of verifying correctness of SIDH public keys, and related statements, as protection against adaptive attacks. Post-scriptum: Some months after this work was completed and made public, the SIDH assumption was broken in a series of papers by several authors. Hence, in the standard SIDH setting, some of the statements studied here now have trivial polynomial time non-interactive proofs. Nevertheless our first sigma protocol is unaffected by the attacks, and our second protocol may still be useful in present and future variants of SIDH that escape the attacks.

The notion of witness encryption introduced by Garg et al. (STOC'13) allows to encrypt a message under a statement $x$ from some NP-language $\mathcal{L}$ with associated relation $(x,w) \in \mathcal{R}$, where decryption can be carried out with the corresponding witness $w$. Unfortunately, known constructions for general-purpose witness encryption rely on strong assumptions, and are mostly of theoretical interest. To address these shortcomings, Goyal et al. (PKC'22) recently introduced a blockchain-based alternative, where a committee decrypts ciphertexts when provided with a valid witness w. Blockchain-based committee solutions have recently gained broad interest to offer security against more powerful adversaries and construct new cryptographic primitives. We follow this line of work, and propose a new notion of statement-oblivious threshold witness encryption. Our new notion offers the functionality of committee-based witness encryption while additionally hiding the statement used for encryption. We present two ways to build statement-oblivious threshold witness encryption, one generic transformation based on anonymous threshold identity-based encryption (A-TIBE) and one direct construction based on bilinear maps. Due to the lack of efficient A-TIBE schemes, the former mainly constitutes a feasibility result, while the latter yields a concretely efficient scheme.

In this paper, we extend Inner-Product Functional Encryption (IPFE), where there is just a vector in the key and a vector in the single sender's ciphertext, to two-client ciphertexts. More precisely, in our two-client functional encryption scheme, there are two data providers who can independently encrypt vectors $\mathbf{x}$ and $\mathbf{y}$ for a data consumer who can, from a functional decryption key associated to a vector $\mathbf{\alpha}$, compute $\sum \alpha_i x_i y_i = \mathbf{x} \cdot \mathsf{Diag}(\mathbf{\alpha}) \cdot \mathbf{y}^\top$. Ciphertexts are linear in the dimension of the vectors, whereas the functional decryption keys are of constant size. We study two interesting particular cases: - 2-party Inner-Product Functional Encryption, with $\mathbf{\alpha}= (1,\ldots,1)$. There is a unique functional decryption key, which enables the computation of $\mathbf{x}\cdot \mathbf{y}^\top$ by a third party, where $\mathbf{x}$ and $\mathbf{y}$ are provided by two independent clients; - Inner-Product Functional Encryption with a Selector, with $\mathbf{x}= \mathbf{x}_0 \| \mathbf{x}_1$ and $\mathbf{y}= \bar{b}^n \| b^n \in \{ 1^n \| 0^n, 0^n \| 1^n \}$, for some bit $b$, on the public coefficients $\mathbf{\alpha} = \mathbf{\alpha}_0 \| \mathbf{\alpha}_1$, in the functional decryption key, so that one gets $\mathbf{x}_b \cdot \mathbf{\alpha}_b^\top$, where $\mathbf{x}$ and $b$ are provided by two independent clients. This result is based on the fundamental Product-Preserving Lemma, which is of independent interest. It exploits Dual Pairing Vector Spaces (DPVS), with security proofs under the $\mathsf{SXDH}$ assumption. We provide two practical applications: to medical diagnosis for the latter IPFE with Selector, and to money-laundering detection for the former 2-party IPFE, both with strong privacy properties, with adaptative security and the use of labels granting a Multi-Client Functional Encryption (MCFE) security for the scheme, thus enabling its use in practical situations.

Pseudorandom correlation functions (PCF), introduced in the work of (Boyle et al., FOCS 2020), allow two parties to locally gen- erate, from short correlated keys, a near-unbounded amount of pseu- dorandom samples from a target correlation. PCF is an extremely ap- pealing primitive in secure computation, where they allow to confine all preprocessing phases of all future computations two parties could want to execute to a single short interaction with low communication and computation, followed solely by offline computations. Beyond in- troducing the notion, Boyle et al. gave a candidate construction, using a new variable-density variant of the learning parity with noise (LPN) assumption. Then, to provide support for this new assumption, the au- thors showed that it provably resists a large class of linear attacks, which captures in particular all known attacks on LPN. In this work, we revisit the analysis of the VDLPN assumption. We make two key contributions: – First, we observe that the analysis of Boyle et al is purely asymp- totic: they do not lead to any concrete and efficient PCF instanti- ation within the bounds that offer security guarantees. To improve this state of affairs, we combine a new variant of a VDLPN assump- tion with an entirely new, much tighter security analysis, which we further tighten using extensive computer simulations to optimize pa- rameters. This way, we manage to obtain for the first time a set of provable usable parameters (under a simple combinatorial conjec- ture which is easy to verify experimentally), leading to a concretely efficient PCF resisting all linear tests. – Second, we identify a flaw in the security analysis of Boyle et al., which invalidates their proof that VDLPN resists linear attacks. Us- ing several new non-trivial arguments, we repair the proof and fully demonstrate that VDLPN resists linear attack; our new analysis is more involved than the original (flawed) analysis. Our parameters set leads to PCFs with keys around 3MB allowing ∼ 500 evaluations per second on one core of a standard laptop for 110 bits of security; these numbers can be improved to 350kB keys and ∼ 3950 evaluations/s using a more aggressive all-prefix variant. All numbers are quite tight: only within a factor 3 of the best bounds one could heuristically hope for.

Multi-signatures have been drawing lots of attention in recent years, due to their applications in cryptocurrencies. Most early constructions require three-round signing, and recent constructions have managed to reduce the round complexity to two. However, their security proofs are mostly based on non-standard, interactive assumptions (e.g. one-more assumptions) and come with a huge security loss, due to multiple uses of rewinding (aka the Forking Lemma). This renders the quantitative guarantees given by the security proof useless. In this work, we improve the state of the art by proposing two efficient two-round multi-signature schemes from the (standard, non-interactive) Decisional Diffie-Hellman (DDH) assumption. Both schemes are proven secure in the random oracle model without rewinding. We do not require any pairing either. Our first scheme supports key aggregation but has a security loss linear in the number of signing queries, and our second scheme is the first tightly secure construction. A key ingredient in our constructions is a new homomorphic dual-mode commitment scheme for group elements, that allows to equivocate for messages of a certain structure. The definition and efficient construction of this commitment scheme is of independent interest.

In this work, we investigate the BGV scheme as implemented in HElib. We begin by performing an implementation-specific noise analysis of BGV. This allows us to derive much tighter bounds than what was previously done. To confirm this, we compare our bounds against the state of the art. We find that, while our bounds are at most $1.8$ bits off the experimentally observed values, they are as much as $29$ bits tighter than previous work. Finally, to illustrate the importance of our results, we propose new and optimised parameters for HElib. In HElib, the special modulus is chosen to be $k$ times larger than the current ciphertext modulus $Q_i$. For a ratio of subsequent ciphertext moduli $\log\left( \frac{Q_i}{Qi−1}\right) = 54$ (a very common choice in HElib), we can optimise $k$ by up to $26$ bits. This means that we can either enable more multiplications without having to switch to larger parameters, or reduce the size of the evaluation keys, thus reducing on communication costs in relevant applications. We argue that our results are near-optimal.

In theory, Fully Homomorphic Encryption schemes allow users to compute any operation over encrypted data. However in practice, one of the major difficulties lies into determining secure cryptographic parameters that minimize the computational cost of evaluating a circuit. In this paper, we propose a solution to solve this open problem. Even though it mainly focuses on TFHE, the method is generic enough to be adapted to all the current FHE schemes. TFHE is particularly suited, for small precision messages, from Boolean to 5-bit integers. It is possible to instantiate bigger integers with this scheme, however the computational cost quickly becomes unpractical. By studying the parameter optimization problem for TFHE, we observed that if one wants to evaluate operations on larger integers, the best way to do it is by encrypting the message into several ciphertexts, instead of considering bigger parameters for a single ciphertext. In the literature, one can find some constructions going in that direction, which are mainly based on radix and CRT representations of the message. However, they still present some limitations, such as inefficient algorithms to evaluate generic homomorphic lookup tables and no solution to work with arbitrary modulus for the message space. We overcome these limitations by proposing two new ways to evaluate homomorphic modular reductions for any modulo in the radix approach, by introducing on the one hand a new hybrid representation, and on the other hand by exploiting a new efficient algorithm to evaluate generic lookup tables on several ciphertexts. The latter is not only a programmable bootstrapping but does not require any padding bit, as needed in the original TFHE bootstrapping. We additionally provide benchmarks to support our results in practice. Finally, we formalize the parameter selection as an optimization problem, and we introduce a framework based on it enabling easy and efficient translation of an arithmetic circuit into an FHE graph of operation along with its optimal set of cryptographic parameters. This framework offers a plethora of features: fair comparisons between FHE operators, study of contexts that are favorable to a given FHE strategy/algorithm, failure probability selection for the entire use case, and so on.

Functional Encryption denotes a form of encryption where a master secret key-holder can control which functions a user can evaluate on encrypted data. Learning With Errors (LWE) (Regev, STOC'05) is known to be a useful cryptographic hardness assumption which implies strong primitives such as, for example, fully homomorphic encryption (Brakerski-Vaikuntanathan, FOCS'11) and lockable obfuscation (Goyal et al., Wichs et al., FOCS'17). Despite its strength, however, there is just a limited number of functional encryption schemes which can be based on LWE. In fact, there are functional encryption schemes which can be achieved by using pairings but for which no secure instantiations from lattice-based assumptions are known: function-hiding inner product encryption (Lin, Baltico et al., CRYPTO'17) and compact quadratic functional encryption (Abdalla et al., CRYPTO'18). This raises the question whether there are some mathematical barriers which hinder us from realizing function-hiding and compact functional encryption schemes from lattice-based assumptions as LWE. To study this problem, we prove an impossibility result for function-hiding functional encryption schemes which meet some algebraic restrictions at ciphertext encryption and decryption. Those restrictions are met by a lot of attribute-based, identity-based and functional encryption schemes whose security stems from LWE. Therefore, we see our results as important indications why it is hard to construct new functional encryption schemes from LWE and which mathematical restrictions have to be overcome to construct secure lattice-based functional encryption schemes for new functionalities.