Microsoft Research Redmond Cryptography Colloquium

Microsoft Research Redmond Cryptography Colloquium

Up Next

SIKE in Hardware for IoT | Reza Azarderakhsh

Reza Azarderakhsh, Florida Atlantic University

Monday, June 17, 2019 | 3:00 PM PDT | 99/1915 Hopper

Abstract

Supersingular Isogeny Key Encapsulation (SIKE) is one of the candidates submitted to NIST’s post-quantum cryptography standardization process. SIKE is the only key exchange mechanism based on isogenies on elliptic curves submitted to NIST standardization process which offers the smallest key-size in comparison to the other candidates. In this talk, we will start with the basics of isogeny-based cryptography and underlying finite field arithmetic computations and describe the SIKE algorithm. We will discuss hardware architectures for secret kernel computations for isogeny maps based on various curves. We will also provide higher level arithmetic overview for isogeny evaluations and isogeny computations which are required for SIKE computations. More specifically, we will provide discussions about isogeny graphs for both Alice and Bob and show how they walk on supersingular isogeny graphs and end up getting a shared secret. We will also provide hardware architectures and illustrate how higher level protocols could get translated and implemented in RTL and programmed into the FPGAs. We will provide performance and area usage results and compare them to the other quantum-safe candidates in similar platforms. Finally, applications will be discussed for IoT world and feasibility of SIKE will be discussed.

Biography

Dr. Reza Azarderakhsh is an assistant professor and I-SENSE Fellow in the Department of Computer Science and Engineering at Florida Atlantic University. He received his PhD. in Computer Engineering from Western University, Canada. After that, he was an post-doc research fellow at the Center for Applied Cryptographic Research, Department of Combinatorics and Optimization at the University of Waterloo which he is currently affiliated as a supervisor member of CryptoWorks21 program there. Dr. Azarderakhsh serves as an Associate Editor of IEEE Transactions on Circuits and Systems (TCAS-I) Cryptographic Engineering track. He is an author/coauthor of more than 80 journals and conference papers in the area of applied cryptography and cryptographic engineering. His research has been supported by NSF, NIST, ARO, NAVY, and Texas Instruments among others. He has developed several algorithms and architectures for classical and post-quantum cryptography including elliptic curve cryptography, isogeny-based cryptography, and lattice-based cryptography systems. He was a recipient of the prestigious NSERC Post-Doctoral Research Fellowship and the Texas Instruments Faculty Award.


Past speakers

Homomorphic Sorting with Better Scalability | Gizem Cetin | June 13, 2019

Homomorphic Sorting with Better Scalability

Gizem Cetin, WPI

Thursday June 13, 201910:30 AM PDT | 99/1927 von Neumann

Abstract

Homomorphic sorting is an operation that blindly sorts a given set of encrypted numbers without decrypting them (thus, there is no need for the secret key). In this work, we propose a new, efficient, and scalable method for homomorphic sorting of numbers: polynomial rank sort algorithm. To put the new algorithm in a comparative perspective, we provide an extensive survey of classical sorting algorithms and networks that are not directly suitable for homomorphic computation. We also include, in our discussions, two of our previous algorithms specifically designed for homomorphic sorting operation: direct sort and greedy sort, and explain howthey evolve from classical sorting networks. We theoretically show that the new algorithm is superior in terms of multiplicative depth when compared with all other algorithms. When batched implementation is used, the number of comparisons is reduced from quadratic to linear in the set size, provided that the number of slots is larger than or equal to the number of elements in the set. Our software implementation results confirm that the new algorithm is several orders of magnitude faster than many methods in the literature. Also, the polynomial sort algorithm scalesbetter than the fastest algorithm in the literature to the best our knowledge although for small sets the execution times are comparable. The proposed algorithm is amenable to parallel implementation as most time consuming operations in the algorithm can naturally be performed concurrently.

Biography

Gizem S. Cetin completed her BS(’12) and MS(’14) degrees in Computer Science and Engineering, at Sabanci University. She was a member of Vernam Lab and recently got her PhD degree from the ECE Department at Worcester Polytechnic Institute. She spent the Summer 2016 as a research intern at Microsoft Research with the Cryptography Group in Redmond, WA. Gizem’s research interest includes software design of cryptosystems, somewhat, leveled and fully homomorphic encryption with a special focus in designing efficient algorithms for FHE/SWHE applications and their software implementations.


Lattice Attacks for Variants of LWE | Shi Bai | June 4, 2019

Lattice Attacks for Variants of LWE

Shi Bai, Florida Atlantic University

Tuesday June 4, 2019 | 1:15 PM PDT | 99/1927 von Neumann

Abstract

The learning with errors (LWE) problem introduced by Regev(STOC’05) is one of the fundamental problems in lattice-based cryptography. It has been used extensively as a security foundation, for public-key encryption, signatures, fully homomorphic encryption (FHE), pseudo-random functions (PRF) and many others. One standard strategy to solve the LWE problem is to reduce it to a unique SVP(uSVP) problem via Kannan’s embedding and then apply a lattice reduction to solve the uSVP problem. In this talk, we will discuss and compare various lattice algorithms for solving LWE, and then give some concrete estimates for breaking various variants of LWE (e.g. generic, small secrets, restricted samples). In the end, we will discuss some recent developments on algorithms for solving LWE.

Biography

Shi Bai is an assistant professor in the Department of Mathematical Sciences at Florida Atlantic University. His research fields are in cryptography and computational number theory. He received his PhD degree in Computer Science from the Australian National University in 2012. He worked as postdoctoral researchers at the University of Auckland (2013-2014) and then at the Ecole Normale Superieure Lyon (2015-2016). He is currently interested in number theoretical algorithms in the cryptanalysis for lattice-based cryptography.


Towards Developer-Centered Cryptographic Ecosystems | Sasha Fahl | May 23, 2019

Towards Developer-Centered Cryptographic Ecosystems

Sasha Fahl, Leibniz University Hannover

Thursday, May 23, 2019 | 2:00 PM PDT | 99/1915 Hopper

Abstract

Potentially dangerous cryptography errors are well documented in many applications. Conventional wisdom suggests that many of these errors are caused by cryptographic Application Programming Interfaces (APIs) that are too complicated, have insecure defaults, or are poorly documented. To address this problem, researchers have created several cryptographic libraries that they claim are more usable.

In this talk, I will present some of my team’s work that addresses specific challenges around making cryptography easier to use for developers. I will discuss multiple studies with developers that focused on different aspects of cryptographic ecosystems, including API usability, the use of documentation, and a study on supporting developers inside their IDE.

Biography

Sascha Fahl is a Professor for Usable Security and Privacy at Leibniz University Hannover in Germany. Previously, he was Professor at Ruhr University Bochum, Germany, held the chair for Information Security at Leibniz University Hannover and was an independent research group leader at CISPA, Saarland University. Prof. Fahl studied Computer Science at Philipps University Marburg and received a Ph.D. in Computer Science. He worked with the Chrome Security team and was a researcher at Fraunhofer FKIE in Bonn. His research won the NSA’s best Scientific Cybersecurity Paper Competition, he received a Google Faculty Research Award and is a recipient of the Heinz Maier-Leibnitz Prize 2018.


Efficient Lattice Trapdoor Sampling and Its Applications | Yuriy Polyakov | April 23, 2019

Efficient Lattice Trapdoor Sampling and Its Applications

Yuriy Polyakov, NJIT

Wednesday, April 23, 2019 | 1:00 PM PDT | 99/1927 von Neumann

Abstract

Lattice trapdoors are used in a wide array of lattice-based cryptographic primitives, including identity-based encryption, attributed-based encryption, functional encryption, program obfuscation, and many others. The main computational bottleneck for many of these cryptographic primitives is lattice trapdoor sampling, which is the key reason why many of these constructions have been impractical. This talk presents efficient Residue-Number-System (RNS) algorithms for lattice trapdoor sampling, and discusses their implementation in the PALISADE library. Our state-of-the-art performance results for several applications based on these algorithms are also presented. These include Gentry-Peikert-Vaikuntanathan digital signature and identity-based encryption, ciphertext-policy and key-policy attribute-based encryption, and obfuscation of conjunction and general branching programs. Our results suggest that some of these implementations are already practical.

Biography

Yuriy Polyakov is an Associate Research Professor at the NJIT Department of Computer Science & Cybersecurity Research Center. His primary research interests are applied lattice-based cryptography, fully homomorphic encryption, program obfuscation, secure genome analysis, and secure computer systems. He is a co-founder and core contributor to the open-source PALISADE Lattice Cryptography Library. Prior to joining NJIT, he worked as a research scientist at MIT CSAIL and held several senior-level industrial positions. His prior research dealt with time series analysis using statistical physics methods and mathematical modeling of membrane technology processes. He received M.S. in Computer Science from NJIT (2003), PhD in Chemical Engineering from Moscow Polytechnic University (2004), and D.Sc.(Dr. Habil.) in Physics & Mathematics from Karpov Institute of Physical Chemistry (2007). He is a recipient of the Moscow Mayor’s Young Scientist Award (2005).


Strong Asymmetric PAKE based on Trapdoor CKEM | Tatiana Bradley | April 17, 2019

Strong Asymmetric PAKE based on Trapdoor CKEM

Tatiana Bradley, University of California, Irvine

Wednesday, April 17, 2019 | 11:00 AM – 12:00 PM PDT | 99/1915 Hopper

Abstract

Password-Authenticated Key Exchange (PAKE) protocols allow two parties that share a password to establish a shared key in a way that is immune to offline attacks. Asymmetric PAKE (aPAKE) adapts this notion to the common client-server setting, where the server stores a one-way hash of the password instead of the password itself, and server compromise allows the adversary to recover the password only via the (inevitable) offline dictionary attack. Most aPAKE protocols, however, allow an attacker to pre-compute a dictionary of hashes, thus instantly learning the user password on server compromise.

Recently, Jarecki, Krawczyk, and Xu formalized a (Universally Composable) strong aPAKE (saPAKE) notion, which requires the password hash to be salted so that all dictionary attack computation must happen after the server compromise leaks the salt and the salted hash. They propose a protocol called OPAQUE, which requires 3 rounds, 3-4 exponentiations per party, and an interactive One-More Diffie-Hellman assumption in the Random Oracle Model (ROM) for security.

We propose an alternative UC strong asymmetric PAKE construction based on a novel use of the encryption+SPHF paradigm for UC PAKE design. Though it also uses ROM, our protocol compares favorably to OPAQUE: it has only two rounds, uses fewer exponentiations, and is based on different assumptions: q-Strong Diffie-Hellman (q-SDH), and the assumptions required to show that the Boneh-Boyen signature function is a Salted Tight One-Way Function (STOWF).

We formalize a UC model for STOWF and analyze the Boneh-Boyen function as UC STOWF in the generic group model (GGM) and ROM. Our saPAKE also uses an implicit-statement trapdoor Conditional Key Encapsulation Mechanism (CKEM), a generalization of SPHF, which forms an extractable commitment to the hashed statement in ROM. This strengthening of SPHF allows for a UC (sa)PAKE design where only the client commits to its password, and only the server performs an SPHF, compared to the standard UC PAKE design paradigm where the encrypt+SPHF subroutine is used symmetrically by both parties.

This talk is based on joint work with Stanislaw Jarecki and Jiayu Xu that is currently under review at CRYPTO 2019.

Biography

Tatiana Bradley is a PhD candidate in Computer Science at UC Irvine. She received a Bachelors degree in Mathematics from Scripps College in 2015.Her research focus is applied cryptography, and, since joining Stanislaw Jarecki’s group at UCI, her research has focused on designing password-authenticated protocols. She has interned at IBM Research in Zurich, and will be interning at Google this summer.


Fully Bideniable Interactive Encryption | Oxana Poburinnaya | Mar 19, 2019

Fully Bideniable Interactive Encryption

Oxana Poburinnaya, Boston University

Tuesday, March 19, 2019 | 1:30 PM – 2:45 PM PDT | 99/1919 Turing

Abstract

While standard encryption guarantees secrecy of the encrypted plaintext only against an attacker that has no knowledge of the communicating parties’ keys and randomness of encryption, deniable encryption [Canetti et al., Crypto’96] provides the additional guarantee that the plaintext remains secret even in face of entities that attempt to coerce (or bribe) the communicating parties to expose their internal states, including the plaintexts, keys and randomness. To achieve this guarantee, deniable encryption equips the parties with faking algorithms which allow them to generate fake keys and randomness that make the ciphertext appear consistent with any plaintext of the parties’ choice. To date, however, only partial results were known: Either deniability against coercing only the sender, or against coercing only the receiver [Sahai-Waters, STOC ‘14] or schemes satisfying weaker notions of deniability [O’Neil et al., Crypto ‘11].

In this paper we present the first fully bideniable interactive encryption scheme, thus resolving the 20-years-old open problem. Our scheme also provides an additional and new guarantee: Even if the sender claims that one plaintext was used and the receiver claims a different one, the adversary has no way of figuring out who is lying the sender, the receiver, or both. This property, which we call off-the-record deniability, is useful when the parties don’t have means to agree on what fake plaintext to claim, or when one party defects against the other. Our protocol has three messages, which is optimal [Bendlin et al., Asiacrypt’11], and needs a globally available reference string. We assume subexponential indistinguishability obfuscation (IO) and one-way functions.

Biography

Oxana is a 6th year PhD student at Boston University, working in theoretical cryptography with Professor Ran Canetti. Prior to joining BU, she studied mathematics at Moscow State University.


Coming Soon

Multidimensional scalar point multiplication algorithms | Koray Karabina | June 18, 2019

Multidimensional scalar point multiplication algorithms

Koray Karabina, Florida Atlantic University

Tuesday, June 18, 2019 | 1:15 PM PDT | 99/1927 von Neumann

Abstract

Elliptic curve groups have been a popular choice in the implementation of traditional and post-quantum cryptographic schemes, including Diffie-Hellman type key-exchange protocols and digital signature algorithms. While some of these applications require to perform multidimensional scalar point multiplication (d-Mul), some of the others enjoy extra speed-ups from utilizing d-Mul with some precomputation or efficiently computable endomorphisms. When the underlying scalars in d-Mul are secret, it is crucial to follow a regular pattern of operations in the implementation because otherwise scalars may be recovered through side channel attacks. Therefore, it has been of great interest to design efficient and secure scalar multiplication algorithms. In this talk, I will give a survey of d-Mul algorithms with some recent theoretical and implementation results.

Biography

Koray Karabina’s research interests are in the areas of design of new cryptographic primitives and algorithms, efficient implementation, and cryptanalysis. He received his Ph.D. degree in Combinatorics and Optimization from the University of Waterloo (UW) in 2010. Koray is currently working as an associate professor in the Department of Mathematical Sciences at Florida Atlantic University (FAU), and he is a member of the Center for Cryptology and Information Security at FAU. Koray’s current research in biometrics is supported by the National Science Foundation, and his research in elliptic curve cryptography is supported by the Army Research Office and the National Institute of Standards and Technology.


Pathfinding in isogeny graphs and computing endomorphism rings | Travis Morrison | June 21, 2019

Pathfinding in isogeny graphs and computing endomorphism rings

Travis Morrison, University of Waterloo

Friday, June 21, 2019 | 1:30 PM PDT | 99/1915 Hopper

Abstract

A large enough quantum computer could run Shor’s algorithm, rendering elliptic curve cryptography insecure. To prepare for a “post-quantum” world, NIST is currently administering a process to standardize one or more cryptographic protocols which should be secure against an attacker with a quantum computer. One submission, SIKE (based on Jao and de Feo’s SIDH) relies on the hardness of pathfinding in supersingular isogeny graphs as an assumption for its security. Supersingular isogeny graphs first appeared in cryptography in the work of Charles, Goren, and Lauter, who used these graphs to build a cryptographic hash function. There is a rich interplay between the geometry of isogenies and the arithmetic of endomorphism rings of elliptic curves, as shown in work of Waterhouse and Kohel, suggesting that one avenue for solving the pathfinding problem is to compute supersingular endomorphism rings.

In this talk, I will discuss heuristic reductions between the pathfinding and endomorphism ring problems. Then, I will discuss recent work with Eisentraeger, Hallgren, Leonardi and Park in which we give several new algorithms for computing supersingular endomorphism rings. I will also discuss to what extent these algorithms may impact the security of SIDH or the CGL isogeny hash.

Biography

Travis Morrison is a post-doctoral fellow working with David Jao and Michele Mosca in the Institute for Quantum Computing at the University of Waterloo. He received his B.A. at the University of California, Santa Cruz. During the summer of 2017, he was an intern at Microsoft Research and was mentored by Kristin Lauter. He received his PhD from the Pennsylvania State University under the supervision of Kirsten Eisentraeger.


PASTA: PASsword-based Threshold Authentication | Peihan Miao | June 24, 2019

PASTA: PASsword-based Threshold Authentication

Peihan Miao, UC Berkeley

Monday, June 24, 2019 | 11:00 AM PDT | 99/1927 von Neumann

Abstract

We introduce and formalize a new notion of password-based threshold token authentication, which protects password-based authentication against single point of failures. Specifically, we distribute the role of a single server among n servers and allow any t servers to collectively verify clients’ passwords and generate tokens, while no t-1 servers can forge a valid token or mount offline dictionary attacks. We then introduce PASTA, a general framework wherein clients can sign on using a two-round (optimal) protocol that meets our strong security guarantees. Our experiments show that the overhead of protecting secrets and credentials against breaches in PASTA, i.e. compared to a naive single-server solution, is extremely low (1-5%) in the most likely setting where client and servers communicate over the internet. The overhead is higher in case of MAC-based tokens over a LAN (though still only a few milliseconds) due to public-key operations in PASTA. We show, however, that this cost is inherent by proving a symmetric-key only solution impossible.

Based on joint work with Shashank Agrawal, Payman Mohassel, and Pratyay Mukherjee: https://eprint.iacr.org/2018/885.pdf.

Biography

Peihan Miao just received her PhD in Cryptography from UC Berkeley (advised by Prof. Sanjam Garg) and will join VISA Research as a research scientist in July. She is primarily interested in the area of secure computation. Her research focuses on building cryptographic tools for achieving the optimal computation, communication, and round complexity in secure computation, aiming for bridging the gap between theory and practice.


Resilience and Vulnerability of Ring-LWE Cryptosystems to Leakage | Dana Dachman-Soled | June 27, 2019

Resilience and Vulnerability of Ring-LWE Cryptosystems to Leakage

Dana Dachman-Soled, University of Maryland

Thursday, June 27, 2019 | 10:30 AM PDT | 99/1915 Hopper

Abstract

One of the foremost avenues for viable post-quantum cryptography is lattice-based cryptography, which primarily involves cryptosystems based on (variants of) the learning with errors (LWE) assumption. While formal leakage resilience guarantees have been well-studied for LWE-based cryptosystems since 2009, the techniques do not carry over to the more efficient, Ring-LWE setting, which is the preferred setting in practice.

In this talk, we will describe information-theoretic and computational approaches for establishing the leakage resilience of Ring-LWE-based cryptosystems. We also present a type of leakage attack known as a partial key exposure attack on Ring-LWE. This attack exploits the algebraic structure of the Ring-LWE setting and is not applicable in the standard LWE setting.

Based on joint work with: Huijing Gong, Mukul Kulkarni and Aria Shahverdi

Biography

Dana Dachman-Soled is an assistant professor in the Department of Electrical and Computer Engineering at the University of Maryland, College Park and is affiliated with the Maryland Cybersecurity Center. She is the recipient of an NSF CAREER award, a Ralph E. Powe Junior Faculty Enhancement award, and a University of Maryland Research and Scholarship (RASA) award. Prior to joining University of Maryland, Dana spent two years as a postdoc at Microsoft Research New England. Before that, she completed her PhD at Columbia University.


Videos