53 research outputs found
Explicit formulas for hashing into G2 on BLS pairing-friendly curves
No full textExplicit formulas for hashing into G2 on BLS pairing-friendly elliptic curve
Efficient hash maps to G2 on BLS curves
No full textWhen a pairing e:G1×G2→GT, on an elliptic curve E defined over a finite field Fq, is exploited for an identity-based protocol, there is often the need to hash binary strings into G1 and G2. Traditionally, if E admits a twist E~ of order d, then G1=E(Fq)∩E[r], where r is a prime integer, and G2=E~(Fqk/d)∩E~[r], where k is the embedding degree of E w.r.t. r. The standard approach for hashing into G2 is to map to a general point P∈E~(Fqk/d) and then multiply it by the cofactor c=#E~(Fqk/d)/r. Usually, the multiplication by c is computationally expensive. In order to speed up such a computation, two different methods—by Scott et al. (International conference on pairing-based cryptography. Springer, Berlin, pp 102–113, 2009) and by Fuentes-Castaneda et al. (International workshop on selected areas in cryptography)—have been proposed. In this paper we consider these two methods for BLS pairing-friendly curves having k∈{12,24,30,42,48}, providing efficiency comparisons. When k=42,48, the application of Fuentes et al. method requires expensive computations which were infeasible for the computational power at our disposal. For these cases, we propose hashing maps that we obtained following Fuentes et al. idea.publishedVersio
Notes on Lattice-Based Cryptography
No full textAsymmetrisk kryptering er avhengig av antakelsen om at noen beregningsproblemer er vanskelige å løse. I 1994 viste Peter Shor at de to mest brukte beregningsproblemene, nemlig det diskrete logaritmeproblemet og primtallsfaktorisering, ikke lenger er vanskelige å løse når man bruker en kvantedatamaskin. Siden den gang har forskere jobbet med å finne nye beregningsproblemer som er motstandsdyktige mot kvanteangrep for å erstatte disse to. Gitterbasert kryptografi er forskningsfeltet som bruker kryptografiske primitiver som involverer vanskelige problemer definert på gitter, for eksempel det korteste vektorproblemet og det nærmeste vektorproblemet. NTRU-kryptosystemet, publisert i 1998, var et av de første som ble introdusert på dette feltet. Problemet Learning With Error (LWE) ble introdusert i 2005 av Regev, og det regnes nå som et av de mest lovende beregningsproblemene som snart tas i bruk i stor skala. Å studere vanskelighetsgraden og å finne nye og raskere algoritmer som løser den, ble et ledende forskningstema innen kryptografi.
Denne oppgaven inkluderer følgende bidrag til feltet:
- En ikke-triviell reduksjon av Mersenne Low Hamming Combination Search Problem, det underliggende problemet med et NTRU-lignende kryptosystem, til Integer Linear Programming (ILP). Særlig finner vi en familie av svake nøkler.
- En konkret sikkerhetsanalyse av Integer-RLWE, en vanskelig beregningsproblemvariant av LWE, introdusert av Gu Chunsheng. Vi formaliserer et meet-in-the-middle og et gitterbasert angrep for denne saken, og vi utnytter en svakhet ved parametervalget gitt av Gu, for å bygge et forbedret gitterbasert angrep.
- En forbedring av Blum-Kalai-Wasserman-algoritmen for å løse LWE. Mer spesifikt, introduserer vi et nytt reduksjonstrinn og en ny gjetteprosedyre til algoritmen. Disse tillot oss å utvikle to implementeringer av algoritmen, som er i stand til å løse relativt store LWE-forekomster. Mens den første effektivt bare bruker RAM-minne og er fullt parallelliserbar, utnytter den andre en kombinasjon av RAM og disklagring for å overvinne minnebegrensningene gitt av RAM.
- Vi fyller et tomrom i paringsbasert kryptografi. Dette ved å gi konkrete formler for å beregne hash-funksjon til G2, den andre gruppen i paringsdomenet, for Barreto-Lynn-Scott-familien av paringsvennlige elliptiske kurver.Public-key Cryptography relies on the assumption that some computational problems are hard to solve. In 1994, Peter Shor showed that the two most used computational problems, namely the Discrete Logarithm Problem and the Integer Factoring Problem, are not hard to solve anymore when using a quantum computer. Since then, researchers have worked on finding new computational problems that are resistant to quantum attacks to replace these two. Lattice-based Cryptography is the research field that employs cryptographic primitives involving hard problems defined on lattices, such as the Shortest Vector Problem and the Closest Vector Problem. The NTRU cryptosystem, published in 1998, was one of the first to be introduced in this field. The Learning With Error (LWE) problem was introduced in 2005 by Regev, and it is now considered one of the most promising computational problems to be employed on a large scale in the near future. Studying its hardness and finding new and faster algorithms that solve it became a leading research topic in Cryptology.
This thesis includes the following contributions to the field:
- A non-trivial reduction of the Mersenne Low Hamming Combination Search Problem, the underlying problem of an NTRU-like cryptosystem, to Integer Linear Programming (ILP). In particular, we find a family of weak keys.
- A concrete security analysis of the Integer-RLWE, a hard computational problem variant of LWE introduced by Gu Chunsheng. We formalize a meet-in-the-middle attack and a lattice-based attack for this case, and we exploit a weakness of the parameters choice given by Gu to build an improved lattice-based attack.
- An improvement of the Blum-Kalai-Wasserman algorithm to solve LWE. In particular, we introduce a new reduction step and a new guessing procedure to the algorithm. These allowed us to develop two implementations of the algorithm that are able to solve relatively large LWE instances. While the first one efficiently uses only RAM memory and is fully parallelizable, the second one exploits a combination of RAM and disk storage to overcome the memory limitations given by the RAM.
- We fill a gap in Pairing-based Cryptography by providing concrete formulas to compute hash-maps to G2, the second group in the pairing domain, for the Barreto-Lynn-Scott family of pairing-friendly elliptic curves.Doktorgradsavhandlin
Don\u27t Use It Twice: Reloaded! On the Lattice Isomorphism Group Action
No full textGroup actions have emerged as a powerful framework in post-quantum cryptography, serving as the foundation for various cryptographic primitives. The Lattice Isomorphism Problem (LIP) has recently gained attention as a promising hardness assumption for designing quantum-resistant protocols. Its formulation as a group action has opened the door to new cryptographic applications, including a commitment scheme and a linkable ring signature.
In this work, we analyze the security properties of the LIP group action and present new findings. Specifically, we demonstrate that it fails to satisfy the weak unpredictability and weak pseudorandomness properties when the adversary has access to as few as three and two instances with the same secret, respectively. This significantly improves upon prior analysis by Budroni et al. (PQCrypto 2024).
As a direct consequence of our findings, we reveal a vulnerability in the linkable ring signature scheme proposed by Khuc et al. (SPACE 2024), demonstrating that the hardness assumption underlying the linkable anonymity property does not hold
Don\u27t Use It Twice: Reloaded! On the Lattice Isomorphism Group Action
No full textGroup actions have emerged as a powerful framework in post-quantum cryptography, serving as the foundation for various cryptographic primitives. The Lattice Isomorphism Problem (LIP) has recently gained attention as a promising hardness assumption for designing quantum-resistant protocols. Its formulation as a group action has opened the door to new cryptographic applications, including a commitment scheme and a linkable ring signature.In this work, we analyze the security properties of the LIP group action and present new findings. Specifically, we demonstrate that it fails to satisfy the weak unpredictability and weak pseudorandomness properties when the adversary has access to as few as three and two instances with the same secret, respectively. This significantly improves upon prior analysis by Budroni et al. (PQCrypto 2024).As a direct consequence of our findings, we reveal a vulnerability in the linkable ring signature scheme proposed by Khuc et al. (SPACE 2024), demonstrating that the hardness assumption underlying the linkable anonymity property does not hold.</p
Don’t Use it Twice! Solving Relaxed Linear Equivalence Problems
No full textThe Linear Code Equivalence (LCE) Problem has received
increased attention in recent years due to its applicability in constructing efficient digital signatures. Notably, the LESS signature scheme based
on LCE is under consideration for the NIST post-quantum standardization process, along with the MEDS signature scheme that relies on an
extension of LCE to the rank metric, namely the Matrix Code Equivalence (MCE) Problem. Building upon these developments, a family of
signatures with additional properties, including linkable ring, group, and
threshold signatures, has been proposed. These novel constructions introduce relaxed versions of LCE (and MCE), wherein multiple samples share
the same secret equivalence. Despite their significance, these variations
have often lacked a thorough security analysis, being assumed to be as
challenging as their original counterparts. Addressing this gap, our work
delves into the sample complexity of LCE and MCE—precisely, the sufficient number of samples required for efficient recovery of the shared
secret equivalence. Our findings reveal, for instance, that one should not
use the same secret twice in the LCE setting since this enables a polynomial time (and memory) algorithm to retrieve the secret. Consequently,
our results unveil the insecurity of two advanced signatures based on
variants of the LCE Problem
Guideline for the Creation of Open Educational Resources : Information and Practical Excercises for Lecturers in Higher Education
No full textUniversity of Graz, 2018
Published by Open Education Austria
Author: Claudia Zimmermann
English translation: Claudia Zimmermann
Sincere thanks to the project team of Open Education Austria: Paolo Budroni, Martin Ebner, Raman Ganguly, Ortrun Gröblinger, Christoph Jokubonis, Michael Kopp, Karin Lach, Sylvia Lingo, Felix Schmitt, Charlotte Zwiauer
Graphic design: Lukas Schnabel & Claudia Zimmermann
This project was funded by the Austrian Federal Ministry of Education, Science and Research.
Legal disclaimer: All information is supplied without warranty. Author and publisher assume no liability
Visions, needs and requirements for Future Research Environments: An Exploration with Historian of Ideas and Science Fiction Author Gwyneth Jones
No full textWe live in remarkable times: the world is changing at an increasing pace, our societies face challenges that extend across national and geographical borders, and we are flooded with (dis)information. The scientific process has already changed extraordinarily in the past half century with research environments evolving from isolated and loosely connected islands to dense networks of researcher and institutional cooperation. In order to develop and explore visions for research, science and society that give us ways into desirable futures an exploration series to consider different perspectives on how research will be conducted in the future was launched. This document contains the interview with Historian of Ideas and Science Fiction Author Gwyneth Jones
Improved Estimation of Key Enumeration with Applications to Solving LWE
No full textIn post-quantum cryptography (PQC), Learning With Errors (LWE) is one of the dominant underlying mathematical problems. For example, in NIST’s PQC standardization process, the Key Encapsulation Mechanism (KEM) protocol chosen for standardization was Kyber, an LWE-based scheme. Recently the dual attack surpassed the primal attack in terms of concrete complexity for solving the underlying LWE problem for multiple cryptographic schemes, including Kyber. The dual attack consists of a reduction part and a distinguishing part. When estimating the cost of the distinguishing part, one has to estimate the expected cost of enumerating over a certain number of positions of the secret key. Our contribution consists of giving a polynomial-time approach for calculating the expected complexity of such an enumeration procedure. This allows us to revise the complexity of the dual attack on the LWE-based protocols Kyber, Saber and TFHE. For all these schemes we improve upon the total bit-complexity in both the classical and the quantum setting.As our method of calculating the expected cost of enumeration is fairly general, it might be of independent interest in other areas of cryptography or even in other research areas
Visions, needs and requirements for Future Research Environments: An Exploration with Computer Scientist and Science Fiction Author Cory Doctorow
No full textWe live in remarkable times: the world is changing at an increasing pace, our societies face challenges that extend across national and geographical borders, and we are flooded with (dis)information. The scientific process has already changed extraordinarily in the past half century with research environments evolving from isolated and loosely connected islands to dense networks of researcher and institutional cooperation. In order to develop and explore visions for research, science and society that give us ways into desirable futures an exploration series to consider different perspectives on how research will be conducted in the future was launched. This document contains the interview with Computer Scientist and Science Fiction Author Cory Doctorow
- …
