International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paulo S. L. M. Barreto

Affiliation: UW Tacoma, USA

Publications

Year
Venue
Title
2015
EPRINT
2015
EPRINT
2014
EPRINT
2010
EPRINT
A new one-time signature scheme from syndrome decoding
Paulo S. L. M. Barreto Rafael Misoczki
We describe a one-time signature scheme based on the hardness of the syndrome decoding problem, and prove it secure in the random oracle model. Our proposal can be instantiated on general linear error correcting codes, rather than restricted families like alternant codes for which a decoding trapdoor is known to exist.
2010
EPRINT
Decoding square-free Goppa codes over $\F_p$
Paulo S. L. M. Barreto Richard Lindner Rafael Misoczki
We propose a new, efficient decoding algorithm for square-free (irreducible or otherwise) Goppa codes over $\F_p$ for any prime $p$. If the code in question has degree $t$ and its average code distance is at least $(4/p)t + 1$, the proposed decoder can uniquely correct up to $(2/p)t$ errors with high probability. The correction capability is higher if the distribution of error magnitudes is not uniform, approaching or reaching $t$ errors when any particular error value occurs much more often than others or exclusively. This makes the method interesting for (semantically secure) cryptosystems based on the decoding problem for permuted and punctured Goppa codes.
2010
EPRINT
A Family of Implementation-Friendly BN Elliptic Curves
We describe a class of Barreto-Naehrig (BN) curves that are not only computationally very simple to generate, but also specially suitable for efficient implementation on the broadest possible range of platforms.
2008
EPRINT
The SIP Security Enhanced by Using Pairing-assisted Massey-Omura Signcryption
Alexandre M. Deusajute Paulo S. L. M. Barreto
Voice over IP (or VoIP) has been adopted progressively not only by a great number of companies but also by an expressive number of people, in Brazil and in other countries. However, this crescent adoption of VoIP in the world brings some concerns such as security risks and threats, mainly on the privacy and integrity of the communication. The risks and threats already exist in the signaling process to the call establishment. This signaling process is performed by specific types of protocols, like the H.323 and SIP (Session Initiation Protocol). Among those risks and threats, we can emphasize the man-in-the-middle attack because of its high danger degree. After doing a bibliographical revision of the current SIP security mechanisms and analyzing some proposals to improve these mechanisms, we verified that the SIP vulnerability to the man-in-the-middle was not totally solved. Then we propose a new security mechanism for SIP in this paper, aiming both to be an alternative security mechanism and a solution for the vulnerability to the man-in-the-middle attack. In our proposal we use a protocol for secure information exchange -- the Massey-Omura protocol -- which, when combined with Pairing-based Cryptography (PBC), provides a better security level for SIP in all its aspects.
2007
EPRINT
On compressible pairings and their computation
Michael Naehrig Paulo S. L. M. Barreto
In this paper we provide explicit formulae to compute bilinear pairings in compressed form, and indicate families of curves where particularly generalised versions of the Eta and Ate pairings due to Zhao \emph{et al.} are especially efficient. With the new formulae it is possible to entirely avoid $\F_{p^k}$ arithmetic during pairing computation on elliptic curves over $\F_p$ with even embedding degree $k$. Using our new method all intermediate results in the Miller loop are represented by just one $\F_{p^{k/2}}$ element and manipulated in compressed form. For certain families of ordinary curves with embedding degree $k = 6m$ all arithmetic can be done in a subfield of size $p^m$ and the representation can be further compressed to two $\F_{p^m}$ elements.
2006
EPRINT
Demonstrating data possession and uncheatable data transfer
D\'ecio Luiz Gazzoni Filho Paulo S\'ergio Licciardi Messeder Barreto
We observe that a certain RSA-based secure hash function is homomorphic. We describe a protocol based on this hash function which prevents `cheating' in a data transfer transaction, while placing little burden on the trusted third party that oversees the protocol. We also describe a cryptographic protocol based on similar principles, through which a prover can demonstrate possession of an arbitrary set of data known to the verifier. The verifier isn't required to have this data at hand during the protocol execution, but rather only a small hash of it. The protocol is also provably as secure as integer factoring.
2006
EPRINT
Hardware Implementation of the $\eta_T$ Pairing in Characteristic 3
Recently, there have been many proposals for secure and novel cryptographic protocols that are built on bilinear pairings. The $\eta_T$ pairing is one such pairing and is closely related to the Tate pairing. In this paper we consider the efficient hardware implementation of this pairing in characteristic 3. All characteristic 3 operations required to compute the pairing are outlined in detail. An efficient, flexible and reconfigurable processor for the $\eta_T$ pairing in characteristic 3 is presented and discussed. The processor can easily be tailored for a low area implementation, for a high throughput implementation, or for a balance between the two. Results are provided for various configurations of the processor when implemented over the field $\mathbb{F}_{3^{97}}$ on an FPGA. As far as we are aware, the processor returns the first characteristic 3 $\eta_T$ pairing in hardware that includes a final exponentiation to a unique value.
2005
ASIACRYPT
2005
CHES
2005
EPRINT
Efficient hardware for the Tate pairing calculation in characteristic three
T. Kerins W. P. Marnane E. M. Popovici P. S. L. M. Barreto
In this paper the benefits of implementation of the Tate pairing computation in dedicated hardware are discussed. The main observation lies in the fact that arithmetic architectures in the extension field $GF(3^{6m})$ are good candidates for parallelization, leading to a similar calculation time in hardware as for operations over the base field $GF(3^m)$. Using this approach an architecture for the hardware implementation of the Tate pairing calculation based on a modified Duursma-Lee algorithm is proposed.
2005
EPRINT
Pairing-Friendly Elliptic Curves of Prime Order
Paulo S. L. M. Barreto Michael Naehrig
Previously known techniques to construct pairing-friendly curves of prime or near-prime order are restricted to embedding degree $k \leqslant 6$. More general methods produce curves over $\F_p$ where the bit length of $p$ is often twice as large as that of the order $r$ of the subgroup with embedding degree $k$; the best published results achieve $\rho \equiv \log(p)/\log(r) \sim 5/4$. In this paper we make the first step towards surpassing these limitations by describing a method to construct elliptic curves of prime order and embedding degree $k = 12$. The new curves lead to very efficient implementation: non-pairing cryptosystem operations only need $\F_p$ and $\F_{p^2}$ arithmetic, and pairing values can be compressed to one \emph{sixth} of their length in a way compatible with point reduction techniques. We also discuss the role of large CM discriminants $D$ to minimize $\rho$; in particular, for embedding degree $k = 2q$ where $q$ is prime we show that the ability to handle $\log(D)/\log(r) \sim (q-3)/(q-1)$ enables building curves with $\rho \sim q/(q-1)$.
2005
EPRINT
On a (Flawed) Proposal to Build More Pairing-Friendly Curves
Michael Scott Paulo S. L. M. Barreto
In a recent letter, Cui, Duan and Chan propose a generalisation of the Scott-Barreto method to build a larger family of MNT curves, and they claim that their proposal is also applicable to other curve construction methods. Here we show that the Cui-Duan-Chan technique is irrecoverably flawed.
2004
CRYPTO
Compressed Pairings
Michael Scott Paulo S. L. M. Barreto
2004
EPRINT
Compressed Pairings
Michael Scott Paulo S. L. M. Barreto
Pairing-based cryptosystems rely on bilinear non-degenerate maps called pairings, such as the Tate and Weil pairings defined over certain elliptic curve groups. In this paper we show how to compress pairing values, how to couple this technique with that of point compression, and how to benefit from the compressed representation to speed up exponentiations involving pairing values, as required in many pairing based protocols.
2004
EPRINT
Generating more MNT elliptic curves
Michael Scott Paulo S.L.M Barreto
In their seminal paper, Miyaji, Nakabayashi and Takano~\cite{miyaji-nakabayashi-takano} describe a simple method for the creation of elliptic curves of prime order with embedding degree 3, 4, or 6. Such curves are important for the realisation of pairing-based cryptosystems on ordinary (non-supersingular) elliptic curves. We provide an alternative derivation of their results, and extend them to allow for the generation of many more suitable curves.
2004
EPRINT
Efficient and Forward-Secure Identity-Based Signcryption
Noel McCullagh Paulo S. L. M. Barreto
Several signcryption schemes proposed in the literature are known to lack semantic security, and semantically secure signcryption schemes tend to be more computationally expensive. In fact, devising an efficient signcryption scheme providing both public verifiability and forward security was until now an open problem. In this paper, we show how a particular kind of signcryption scheme may become completely insecure when implemented with certain efficient instantiations of the Tate or Weil pairing. We also address the drawbacks of the secure schemes by proposing efficient, semantically and forward-secure signcryption schemes, in both transferable and non-transferable form, that can be realised on top of any pairing instantiation. As a bonus, we also derive from them a new, efficient identity-based signature scheme.
2004
EPRINT
A New Two-Party Identity-Based Authenticated Key Agreement
Noel McCullagh Paulo S. L. M. Barreto
We present a new two-party identity-based key agreement that is more efficient than previously proposed schemes. It is inspired on a new identity-based key pair derivation algorithm first proposed by Sakai and Kasahara. We show how this key agreement can be used in either escrowed or escrowless mode. We also describe conditions under which users of different Key Generation Centres can agree on a shared secret key. We give an overview of existing two-party key agreement protocols, and compare our new scheme with existing ones in terms of computational cost and storage requirements.
2004
EPRINT
A note on efficient computation of cube roots in characteristic 3
Paulo S. L. M. Barreto
The cost of the folklore algorithm for computing cube roots in $\F_{3^m}$ in standard polynomial basis is less that one multiplication, but still $O(m^2)$. Here we show that, if $\F_{3^m}$ is represented in trinomial basis as $\F_3[x]/(x^m + ax^k + b)$ with $a, b = \pm 1$, the actual cost of computing cube roots in $\F_{3^m}$ is only $O(m)$.
2004
EPRINT
Efficient Pairing Computation on Supersingular Abelian Varieties
We present a general technique for the efficient computation of pairings on supersingular Abelian varieties. This formulation, which we call the eta pairing, generalises results of Duursma and Lee for computing the Tate pairing on supersingular elliptic curves in characteristic three. We then show how our general technique leads to a new algorithm which is about twice as fast as the Duursma-Lee method. These ideas are then used for elliptic and hyperelliptic curves in characteristic 2 with very efficient results. In particular, the hyperelliptic case is faster than all previously known pairing algorithms.
2004
JOFC
2003
EPRINT
On the Selection of Pairing-Friendly Groups
Paulo S. L. M. Barreto Ben Lynn Michael Scott
We propose a simple algorithm to select group generators suitable for pairing-based cryptosystems. The selected parameters are shown to favor implementations of the Tate pairing that are at once conceptually simple and efficient, with an observed performance about 2 to 10 times better than previously reported implementations, depending on the embedding degree. Our algorithm has beneficial side effects: various non-pairing operations become faster, and bandwidth may be saved.
2002
CRYPTO
2002
EPRINT
Efficient Algorithms for Pairing-Based Cryptosystems
Paulo S.L.M. Barreto Hae Y. Kim Ben Lynn Michael Scott
We describe fast new algorithms to implement recent cryptosystems based on the Tate pairing. In particular, our techniques improve pairing evaluation speed by a factor of about 55 compared to previously known methods in characteristic 3, and attain performance comparable to that of RSA in larger characteristics. We also propose faster algorithms for scalar multiplication in characteristic 3 and square root extraction over $\GF{p^m}$, the latter technique being also useful in contexts other than that of pairing-based cryptography.
2002
EPRINT
Constructing Elliptic Curves with Prescribed Embedding Degrees
Paulo S. L. M. Barreto Ben Lynn Michael Scott
Pairing-based cryptosystems depend on the existence of groups where the Decision Diffie-Hellman problem is easy to solve, but the Computational Diffie-Hellman problem is hard. Such is the case of elliptic curve groups whose embedding degree is large enough to maintain a good security level, but small enough for arithmetic operations to be feasible. However, the embedding degree is usually enormous, and the scarce previously known suitable elliptic groups had embedding degree $k \leqslant 6$. In this note, we examine criteria for curves with larger $k$ that generalize prior work by Miyaji et al. based on the properties of cyclotomic polynomials, and propose efficient representations for the underlying algebraic structures.
2001
FSE
2001
EPRINT
SQUARE Attacks on Reduced-Round PES and IDEA Block Ciphers
This paper reports on variants of the Square attack applied to reduced-round versions of the PES and IDEA block ciphers. Attacks on 2.5 rounds of IDEA require $3\cdot 2^{16}$ chosen-plaintexts and recover 78 key bits. A new kind of attack, the Square related-key attack, is applied on 2.5 rounds of IDEA and recovers 32 key bits, with 2 chosen-plaintexts and $2^{17}$ related keys. Similar results hold for 2.5 rounds of PES. Implementations of the attacks on 32-bit block mini-versions of both ciphers confirmed the expected computational complexity. Although our attacks do not improve on previous approaches, this report shows new variants of the Square attack on word-oriented block ciphers like IDEA and PES.
2001
EPRINT
Fast hashing onto elliptic curves over fields of characteristic 3
Paulo S. L. M. Barreto Hae Yong Kim
We describe a fast hash algorithm that maps arbitrary messages onto points of an elliptic curve defined over a finite field of characteristic 3. Our new scheme runs in time $O(m^2)$ for curves over $\GF{3^m}$. The best previous algorithm for this task runs in time $O(m^3)$. Experimental data confirms the speedup by a factor $O(m)$, or approximately a hundred times for practical $m$ values. Our results apply for both standard and normal basis representations of $\GF{3^m}$.

Program Committees

Asiacrypt 2019
Eurocrypt 2019
Eurocrypt 2018
PKC 2016
Crypto 2015
Asiacrypt 2014
PKC 2014
CHES 2012
Crypto 2011
CHES 2011
Eurocrypt 2009
Asiacrypt 2006
PKC 2006
Asiacrypt 2005