Browse ORBi

- What it is and what it isn't
- Green Road / Gold Road?
- Ready to Publish. Now What?
- How can I support the OA movement?
- Where can I learn more?

ORBi

TOPICS IN COMPUTATIONAL NUMBER THEORY AND CRYPTANALYSIS - On Simultaneous Chinese Remaindering, Primes, the MiNTRU Assumption, and Functional Encryption Barthel, Jim Jean-Pierre Doctoral thesis (2022) This thesis reports on four independent projects that lie in the intersection of mathematics, computer science, and cryptology: Simultaneous Chinese Remaindering: The classical Chinese Remainder Problem ... [more ▼] This thesis reports on four independent projects that lie in the intersection of mathematics, computer science, and cryptology: Simultaneous Chinese Remaindering: The classical Chinese Remainder Problem asks to find all integer solutions to a given system of congruences where each congruence is defined by one modulus and one remainder. The Simultaneous Chinese Remainder Problem is a direct generalization of its classical counterpart where for each modulus the single remainder is replaced by a non-empty set of remainders. The solutions of a Simultaneous Chinese Remainder Problem instance are completely defined by a set of minimal positive solutions, called primitive solutions, which are upper bounded by the lowest common multiple of the considered moduli. However, contrary to its classical counterpart, which has at most one primitive solution, the Simultaneous Chinese Remainder Problem may have an exponential number of primitive solutions, so that any general-purpose solving algorithm requires exponential time. Furthermore, through a direct reduction from the 3-SAT problem, we prove first that deciding whether a solution exists is NP-complete, and second that if the existence of solutions is guaranteed, then deciding whether a solution of a particular size exists is also NP-complete. Despite these discouraging results, we studied methods to find the minimal solution to Simultaneous Chinese Remainder Problem instances and we discovered some interesting statistical properties. A Conjecture On Primes In Arithmetic Progressions And Geometric Intervals: Dirichlet’s theorem on primes in arithmetic progressions states that for any positive integer q and any coprime integer a, there are infinitely many primes in the arithmetic progression a + nq (n ∈ N), however, it does not indicate where those primes can be found. Linnik’s theorem predicts that the first such prime p0 can be found in the interval [0;q^L] where L denotes an absolute and explicitly computable constant. Albeit only L = 5 has been proven, it is widely believed that L ≤ 2. We generalize Linnik’s theorem by conjecturing that for any integers q ≥ 2, 1 ≤ a ≤ q − 1 with gcd(q, a) = 1, and t ≥ 1, there exists a prime p such that p ∈ [q^t;q^(t+1)] and p ≡ a mod q. Subsequently, we prove the conjecture for all sufficiently large exponent t, we computationally verify it for all sufficiently small modulus q, and we investigate its relation to other mathematical results such as Carmichael’s totient function conjecture. On The (M)iNTRU Assumption Over Finite Rings: The inhomogeneous NTRU (iNTRU) assumption is a recent computational hardness assumption, which claims that first adding a random low norm error vector to a known gadget vector and then multiplying the result with a secret vector is sufficient to obfuscate the considered secret vector. The matrix inhomogeneous NTRU (MiNTRU) assumption essentially replaces vectors with matrices. Albeit those assumptions strongly remind the well-known learning-with-errors (LWE) assumption, their hardness has not been studied in full detail yet. We provide an elementary analysis of the corresponding decision assumptions and break them in their basis case using an elementary q-ary lattice reduction attack. Concretely, we restrict our study to vectors over finite integer rings, which leads to a problem that we call (M)iNTRU. Starting from a challenge vector, we construct a particular q-ary lattice that contains an unusually short vector whenever the challenge vector follows the (M)iNTRU distribution. Thereby, elementary lattice reduction allows us to distinguish a random challenge vector from a synthetically constructed one. A Conditional Attack Against Functional Encryption Schemes: Functional encryption emerged as an ambitious cryptographic paradigm supporting function evaluations over encrypted data revealing the result in plain. Therein, the result consists either in a valid output or a special error symbol. We develop a conditional selective chosen-plaintext attack against the indistinguishability security notion of functional encryption. Intuitively, indistinguishability in the public-key setting is based on the premise that no adversary can distinguish between the encryptions of two known plaintext messages. As functional encryption allows us to evaluate functions over encrypted messages, the adversary is restricted to evaluations resulting in the same output only. To ensure consistency with other primitives, the decryption procedure of a functional encryption scheme is allowed to fail and output an error. We observe that an adversary may exploit the special role of these errors to craft challenge messages that can be used to win the indistinguishability game. Indeed, the adversary can choose the messages such that their functional evaluation leads to the common error symbol, but their intermediate computation values differ. A formal decomposition of the underlying functionality into a mathematical function and an error trigger reveals this dichotomy. Finally, we outline the impact of this observation on multiple DDH-based inner-product functional encryption schemes when we restrict them to bounded-norm evaluations only. [less ▲] Detailed reference viewed: 27 (2 UL)On the (M)iNTRU assumption in the integer case Barthel, Jim Jean-Pierre ; Müller, Volker ; Rosie, Razvan in Qiong, Huang; Yu, Yu (Eds.) Provable and Practical Security, 15th International Conference, ProvSec 2021, Guangzhou, November 5 – November 8, 2021, Proceedings (2021, November 02) In AsiaCrypt 2019, Genise, Gentry, Halevi, Li and Micciancio put forth two novel and intriguing computational hardness hypotheses: The inhomogeneous NTRU (iNTRU) assumption and its matrix version MiNTRU ... [more ▼] In AsiaCrypt 2019, Genise, Gentry, Halevi, Li and Micciancio put forth two novel and intriguing computational hardness hypotheses: The inhomogeneous NTRU (iNTRU) assumption and its matrix version MiNTRU. In this work, we break the integer case of the iNTRU assumption through elementary lattice reduction, and we describe how the attack might be generalized to polynomial rings and to the low dimensional MiNTRU assumption with small noise. [less ▲] Detailed reference viewed: 175 (14 UL)Partitioned Searchable Encryption Barthel, Jim Jean-Pierre ; ; et al in Qiong, Huang; Yu, Yu (Eds.) Provable and Practical Security, 15th International Conference, ProvSec 2021, Guangzhou, November 5 – November 8, 2021, Proceedings (2021, November 02) Symmetric searchable encryption (SSE) allows to outsource encrypted data to an untrusted server and retain searching capabilities. This is done without impacting the privacy of both the data and the ... [more ▼] Symmetric searchable encryption (SSE) allows to outsource encrypted data to an untrusted server and retain searching capabilities. This is done without impacting the privacy of both the data and the search/update queries. In this work we put forth a new flavour of symmetric searchable encryption (SSE): Partitioned SSE is meant to capture the cases where the search rights must be partitioned among multiple individuals. We motivate through compelling examples the practical need for such a notion and discuss instantiations based on functional encryption and trapdoor permutations. First we leverage the power of functional encryption (FE). Our construction follows the general technique of encrypting the set of keywords and the presumably larger datafiles separately, a keyword acting as a ``pointer'' to datafiles it belongs to. To improve on the constraint factors (large ciphertext, slow encryption/decryption procedures) that are inherent in FE schemes, the keyword check is done with the help of a Bloom filter -- one per datafile: the crux idea is to split the filter into buckets, and encrypt each bucket separately under an FE scheme. Functional keys are given for binary \masks checking if relevant positions are set to 1 inside the underlying bit-vector of the Bloom filter. The second construction we present achieves forward security and stems from the scheme by Bost in CCS'16. We show that a simple tweak of the original construction gives rise to a scheme supporting updates in the partitioned setting. Moreover, the constructions take into account the possibility that some specific users are malicious while declaring their search results. [less ▲] Detailed reference viewed: 162 (4 UL)NIKE from Affine Determinant Programs Barthel, Jim Jean-Pierre ; Rosie, Razvan in Qiong, Huang; Yu, Yu (Eds.) Provable and Practical Security, 15th International Conference, ProvSec 2021, Guangzhou, November 5 – November 8, 2021, Proceedings (2021, November 02) A multi-party non-interactive key-exchange (NIKE) scheme enables N users to securely exchange a secret key K in a non-interactive manner. It is well-known that NIKE schemes can be obtained assuming the ... [more ▼] A multi-party non-interactive key-exchange (NIKE) scheme enables N users to securely exchange a secret key K in a non-interactive manner. It is well-known that NIKE schemes can be obtained assuming the existence of indistinguishability obfuscation (iO). In this work, we revisit the original, iO-based, provably-secure NIKE construction by Boneh and Zhandry, aiming to simplify it. The core idea behind our protocol is to replace the functionality of the obfuscator with the one of an affine determinant program (ADP). Although ADPs have been designed with the purpose of attaining indistinguishability obfuscation, such implication is left open for general circuits. The ingredients enabling to prove the security of our scheme stem into a more careful analysis of the branching programs needed to build ADPs. In particular, we show: 1) An intuitive indistinguishability notion defined for ADPs of puncturable pseudorandom functions (PRFs) is sufficient to prove security for NIKE. 2) A set of simple conditions based on ADP's branching program topology that are sufficient for proving indistinguishability of ADPs. We leave open the question of finding ADPs satisfying them. [less ▲] Detailed reference viewed: 82 (7 UL)A Simple Inner-Product Functional Encryption Scheme from the Inverse-DDH Assumption Barthel, Jim Jean-Pierre ; Rosie, Razvan ; Sahu, Rajeev Anand E-print/Working paper (n.d.) Detailed reference viewed: 132 (29 UL)New Constructions of Verifiable Delay Functions Barthel, Jim Jean-Pierre ; Rosie, Razvan E-print/Working paper (n.d.) Detailed reference viewed: 145 (10 UL)On basis vectors of lattices Barthel, Jim Jean-Pierre ; Müller, Volker E-print/Working paper (n.d.) Integer lattices enjoy increasing interest among mathematicians and cryptographers. However, there are still many elementary open questions, like finding specific vectors or particular bases of a given ... [more ▼] Integer lattices enjoy increasing interest among mathematicians and cryptographers. However, there are still many elementary open questions, like finding specific vectors or particular bases of a given lattice. Our study consists in exhibiting which integer vectors may be chosen as basis vectors of a chosen lattice. The compelling part of our development is that this condition is obtained through an unusual application of Dirichlet's Theorem on primes in arithmetic progressions and that it has a surprising consequence for vectors achieving the successive minima. [less ▲] Detailed reference viewed: 42 (3 UL)A conjecture on primes in arithmetic progressions and geometric intervals Barthel, Jim Jean-Pierre ; Müller, Volker E-print/Working paper (n.d.) We conjecture that any interval of the form [q^t ,q^(t+1) ], where q≥ 2 and t≥1 denote positive integers, contains at least one prime from each coprime congruence class. We prove this conjecture first ... [more ▼] We conjecture that any interval of the form [q^t ,q^(t+1) ], where q≥ 2 and t≥1 denote positive integers, contains at least one prime from each coprime congruence class. We prove this conjecture first unconditionally for all 2≤q≤45000 and all t≥1 and second under ERH for almost all q≥2 and all t≥2. Furthermore, we outline heuristic arguments for the validity of the conjecture beyond the proven bounds and we compare it with related long-standing conjectures. Finally, we discuss some of its consequences. [less ▲] Detailed reference viewed: 48 (8 UL)ON THE (NON-)EQUIVALENCE OF INTEGRAL BINARY QUADRATIC FORMS AND THEIR NEGATIVE FORMS Barthel, Jim Jean-Pierre ; Müller, Volker E-print/Working paper (n.d.) Integral binary quadratic forms have been extensively studied in order to compute the class number of real and complex quadratic ﬁelds. Many studies restricted the equivalence class of quadratic forms or ... [more ▼] Integral binary quadratic forms have been extensively studied in order to compute the class number of real and complex quadratic ﬁelds. Many studies restricted the equivalence class of quadratic forms or identiﬁed speciﬁc forms in order to compute the class number through enumeration of equivalence classes. One often used assumption is that a given form and its negative are equivalent or are synthetically identiﬁed. This document presents a concise Lagrangian approach to integral binary quadratic forms, outlines the equivalence classes in its broadest sense and uses it to develop a general condition when a given integral binary quadratic form and its negative are equivalent. Then, the existence of integral binary quadratic forms which are non-equivalent to their negatives is proven and an elementary algorithm to determine the (non-)equivalence of a given form and its negative is outlined. [less ▲] Detailed reference viewed: 90 (6 UL) |
||