IACR News
Updates on the COVID-19 situation are on the
Announcement channel.
Here you can see all recent updates to the IACR webpage. These updates are also available:
09 July 2022
Kyoto, Japan, 19 June - 22 June 2023
Event date: 19 June to 22 June 2023
Submission deadline: 8 September 2022
Notification: 10 November 2022
Submission deadline: 8 September 2022
Notification: 10 November 2022
08 July 2022
Corentin Le Coz, Christopher Battarbee, Ramón Flores, Thomas Koberda, Delaram Kahrobaei
We define new families of Tillich-Zémor hash functions, using higher dimensional special linear groups over finite fields as platforms.
The Cayley graphs of these groups combine fast mixing properties and high girth, which
together give rise to good preimage and collision resistance of the
corresponding hash functions. We justify the claim that the resulting
hash functions are post-quantum secure.
Anna Lysyanskaya
A blind signature scheme is a digital signature scheme that allows the signature recipient to obtain a digital signature on a message of her choice without revealing anything about the message or the resulting signature to the signer. Blind signature schemes have recently found applications for privacy-preserving web browsing and ad ecosystems, and as such, are ripe for standardization.
Recently, Denis, Jacobs and Wood [18, 17] submitted an IETF draft for a standard for a blind version of RSA-PSS. Here, we show that this proposed standard constitutes a one-more unforgeable blind signature scheme in the random-oracle model under the one-more-RSA assumption. Further, we show that the blind version of RSA-FDH proposed and analyzed by Bellare, Namprempre, Pointcheval and Semanko does not satisfy blindness when the public key (N,e) is chosen maliciously, but satisfies a weaker notion of a blind token.
Recently, Denis, Jacobs and Wood [18, 17] submitted an IETF draft for a standard for a blind version of RSA-PSS. Here, we show that this proposed standard constitutes a one-more unforgeable blind signature scheme in the random-oracle model under the one-more-RSA assumption. Further, we show that the blind version of RSA-FDH proposed and analyzed by Bellare, Namprempre, Pointcheval and Semanko does not satisfy blindness when the public key (N,e) is chosen maliciously, but satisfies a weaker notion of a blind token.
Lei Xu, Anxin Zhou, Huayi Duan, Cong Wang, Qian Wang, Xiaohua Jia
Encrypted database draws much attention as it provides privacy-protection services for sensitive data outsourced to a third party. Recent studies show that the security guarantee of encrypted databases are challenged by several leakage-abuse attacks on its search module, and corresponding countermeasures are also proposed. Most of these studies focus on static databases, yet the case for dynamic has not been well investigated. To fill this gap, in this paper, we focus on exploring privacy risks in dynamic encrypted databases and devising effective mitigation techniques. To begin with, we systematically study the exploitable information disclosed during the database querying process, and consider two types of attacks that can recover encrypted queries. The first active attack works by injecting encoded files and correlating file volume information. The second passive attack works by identifying queries’ unique relational characteristics across updates, assuming certain background knowledge of plaintext databases. To mitigate these attacks, we propose a two-layer encrypted database hardening approach, which obfuscates both search indexes and files in a continuous way. As a result, the unique characteristics emerging after data updates can be eliminated constantly. We conduct a series of experiments to confirm the severity of our attacks and the effectiveness of our countermeasures.
Edimar Veríssimo da Silva
NJS is a cryptographic protection algorithm for relational databases with non-deterministic symmetric encryption, making it possible to search data with almost the same speed as a clear text search (depending on the parameterization). The algorithm has the characteristic of performing a fast encryption on the data and a slightly slower decryption that is only performed on the client workstation. The entire process of searching, changing, adding and deleting data is performed on the server with the encrypted data. The NJS cipher is not a form of homomorphic encryption, but it can replace it with some search limitations. One advantage is the fact that noise added to the message does not interfere with its decryption, regardless of the number of operations performed on each record in a database table.
Jean-Luc Watson, Sameer Wagh, Raluca Ada Popa
Secure multi-party computation (MPC) is an essential tool for privacy-preserving machine learning (ML). However, secure training of large-scale ML models currently requires a prohibitively long time to complete. Given that large ML inference and training tasks in the plaintext setting are significantly accelerated by Graphical Processing Units (GPUs), this raises the natural question: can secure MPC leverage GPU acceleration? A few recent works have studied this question in the context of accelerating specific components or protocols, but do not provide a general-purpose solution. Consequently, MPC developers must be both experts in cryptographic protocol design and proficient at low-level GPU kernel development to achieve good performance on any new protocol implementation.
We present Piranha, a general-purpose, modular platform for accelerating secret sharing-based MPC protocols using GPUs. Piranha allows the MPC community to easily leverage the benefits of a GPU without requiring GPU expertise. Piranha contributes a three-layer architecture: (1) a device layer that can independently accelerate secret-sharing protocols by providing integer-based kernels absent in current general-purpose GPU libraries, (2) a modular protocol layer that allows developers to maximize utility of limited GPU memory with in-place computation and iterator-based support for non-standard memory access patterns, and (3) an application layer that allows applications to remain completely agnostic to the underlying protocols they use.
To demonstrate the benefits of Piranha, we implement 3 state-of-the-art linear secret sharing MPC protocols for secure NN training: 2-party SecureML (IEEE S&P ’17), 3-party Falcon (PETS ’21), and 4-party FantasticFour (USENIX Security ’21). Compared to their CPU-based implementations, the same protocols implemented on top of Piranha’s protocol-agnostic acceleration exhibit a 16−48× decrease in training time. For the first time, Piranha demonstrates the feasibility of training a realistic neural network (e.g. VGG), end-to-end, using MPC in a little over one day. Piranha is open source and available at https://github.com/ucbrise/piranha.
We present Piranha, a general-purpose, modular platform for accelerating secret sharing-based MPC protocols using GPUs. Piranha allows the MPC community to easily leverage the benefits of a GPU without requiring GPU expertise. Piranha contributes a three-layer architecture: (1) a device layer that can independently accelerate secret-sharing protocols by providing integer-based kernels absent in current general-purpose GPU libraries, (2) a modular protocol layer that allows developers to maximize utility of limited GPU memory with in-place computation and iterator-based support for non-standard memory access patterns, and (3) an application layer that allows applications to remain completely agnostic to the underlying protocols they use.
To demonstrate the benefits of Piranha, we implement 3 state-of-the-art linear secret sharing MPC protocols for secure NN training: 2-party SecureML (IEEE S&P ’17), 3-party Falcon (PETS ’21), and 4-party FantasticFour (USENIX Security ’21). Compared to their CPU-based implementations, the same protocols implemented on top of Piranha’s protocol-agnostic acceleration exhibit a 16−48× decrease in training time. For the first time, Piranha demonstrates the feasibility of training a realistic neural network (e.g. VGG), end-to-end, using MPC in a little over one day. Piranha is open source and available at https://github.com/ucbrise/piranha.
Sukanta Dey, Jungmin Park, Nitin Pundir, Dipayan Saha, Amit Mazumder Shuvo, Dhwani Mehta, Navid Asadi, Fahim Rahman, Farimah Farahmandi, Mark Tehranipoor
An integrated circuit is subject to a number of attacks including information leakage, side-channel attacks, fault-injection, malicious change, reverse engineering, and piracy. Majority of these attacks take advantage of physical placement and routing of cells and interconnects. Several measures have already been proposed to deal with security issues of the high level functional design and logic synthesis. However, to ensure end-to-end trustworthy IC design flow, it is necessary to have security sign-off during physical design flow. This paper presents a secure physical design roadmap to enable end-to-end trustworthy IC design flow. The paper also discusses utilization of AI/ML to establish security at the layout level. Major research challenges in obtaining a secure physical design are also discussed.
07 July 2022
Cristian-Alexandru Botocan
Side-channel attacks are powerful non-invasive attacks on cryptographic algorithms. Among such attacks, profiling attacks have a prominent place as they assume an attacker with access to a copy of the device under attack. The attacker uses the device's copy to learn as much as possible about the device and then mount the attack on the target device. In the last few years, Machine Learning has been successfully used in profiling attacks, as such techniques proved to be capable of breaking implementations protected with countermeasures.
In the deep learning-based profiling attack, a core problem is finding efficient neural network architectures to evaluate an implementation's security correctly. Unfortunately, this process is time-consuming, and a different neural network configuration usually needs to be defined for every target. Hence, we propose the following process: train a separate autoencoder for each dataset obtained from different cryptographic implementations and devices to receive an encoded version for each one. After that, define a universal model that can break multiple (encoded) datasets. Thus, instead of finding dataset-specific neural network architectures, we reduce the effort to find autoencoders to encode the datasets and a single neural network to break~them.
In the deep learning-based profiling attack, a core problem is finding efficient neural network architectures to evaluate an implementation's security correctly. Unfortunately, this process is time-consuming, and a different neural network configuration usually needs to be defined for every target. Hence, we propose the following process: train a separate autoencoder for each dataset obtained from different cryptographic implementations and devices to receive an encoded version for each one. After that, define a universal model that can break multiple (encoded) datasets. Thus, instead of finding dataset-specific neural network architectures, we reduce the effort to find autoencoders to encode the datasets and a single neural network to break~them.
Russell W. F. Lai, Giulio Malavolta, Nicholas Spooner
We investigate the security of succinct arguments against quantum adversaries. Our main result is a proof of knowledge-soundness in the post-quantum setting for a class of multi-round interactive protocols, including those based on the recursive folding technique of Bulletproofs.
To prove this result, we devise a new quantum rewinding strategy, the first that allows for rewinding across many rounds. This technique applies to any protocol satisfying natural multi-round generalizations of special soundness and collapsing. For our main result, we show that recent Bulletproofs-like protocols based on lattices satisfy these properties, and are hence sound against quantum adversaries.
To prove this result, we devise a new quantum rewinding strategy, the first that allows for rewinding across many rounds. This technique applies to any protocol satisfying natural multi-round generalizations of special soundness and collapsing. For our main result, we show that recent Bulletproofs-like protocols based on lattices satisfy these properties, and are hence sound against quantum adversaries.
David Chaum, Mario Larangeira, Mario Yaksetig
Recently, Chaum et al. (ACNS'21) introduced $\mathcal{S}_{leeve}$, which describes an extra security layer for signature schemes, i.e., ECDSA. This distinctive feature is a new key generation mechanism, allowing users to generate a ''back up key'' securely nested inside the secret key of a signature scheme.
Using this novel construction, the ''back up key'', which is secret, can be used to generate a ''proof of ownership'', i.e., only the rightful owner of this secret key can generate such a proof. This design offers a quantum secure fallback, i.e., a brand new quantum resistant signature, ready to be used, nested in the ECDSA secret key. In this work, we rely on the original $\mathcal{S}_{leeve}$ definition to generalize the construction to a modular design based on Tweakable Hash Functions, thus yielding a cleaner design of the primitive. Furthermore, we provide a thorough security analysis taking into account the security of the ECDSA signature scheme, which is lacking in the original work. Finally, we provide an analysis based on formal methods using Verifpal assuring the security guarantees our construction provides.
Yuval Ishai, Dakshita Khurana, Amit Sahai, Akshayaram Srinivasan
We give black-box, round-optimal protocol compilers from semi-honest security to malicious security in the Random Oracle Model (ROM) and in the 1-out-of-2 oblivious transfer (OT) correlations model. We use our compilers to obtain the following black-box constructions of general-purpose protocols for secure computation tolerating static, malicious corruptions of all-but-one participants:
\begin{itemize}
\item A two-round, two-party protocol
in the random oracle model, making black-box use of a two-round semi-honest secure protocol. Prior to our work, such a result was not known even for special functionalities such as OT. As an application, we get efficient constructions of two-round malicious OT/OLE in the random oracle model based on a black-box use of two-round semi-honest OT/OLE.
\item A three-round multiparty protocol in the random oracle model, making a black-box use of two-round semi-honest OT. This protocol matches a known round complexity lower bound due to Applebaum et al. (ITCS 2020) and is based on a minimal cryptographic primitive.
\item A two-round multiparty protocol in the OT correlations model, making a black-box use of a semi-malicious protocol. This improves over a similar protocol of the authors (Crypto 2021) by eliminating an adaptive security requirement and replacing nonstandard multiparty OT correlations by standard ones. As an application, we get 2-round protocols for arithmetic branching programs that make a black-box use of the underlying field. \end{itemize}
As a contribution of independent interest, we provide a new variant of the IPS compiler (Ishai, Prabhakaran and Sahai, Crypto 2008) in the two-round setting, where we relax requirements on the IPS ``inner protocol'' by strengthening the ``outer protocol''.
\item A two-round multiparty protocol in the OT correlations model, making a black-box use of a semi-malicious protocol. This improves over a similar protocol of the authors (Crypto 2021) by eliminating an adaptive security requirement and replacing nonstandard multiparty OT correlations by standard ones. As an application, we get 2-round protocols for arithmetic branching programs that make a black-box use of the underlying field. \end{itemize}
As a contribution of independent interest, we provide a new variant of the IPS compiler (Ishai, Prabhakaran and Sahai, Crypto 2008) in the two-round setting, where we relax requirements on the IPS ``inner protocol'' by strengthening the ``outer protocol''.
Hyunji Kim, Sejin Lim, Yeajun Kang, Wonwoong Kim, Hwajeong Seo
Cryptanalysis is to infer the secret key of cryptography algorithm. There are brute-force attack, differential attack, linear attack, and chosen plaintext attack.
With the development of artificial intelligence, deep learning-based cryptanalysis has been actively studied. There are works in which known-plaintext attacks against lightweight block ciphers, such as S-DES, have been performed. In this paper, we propose a cryptanalysis method based on the-state-of-art deep learning technologies (e.g. residual connections and gated linear units) for lightweight block ciphers (e.g. S-DES and S-AES).
The number of parameters required for training is significantly reduced by 93.16~\% and the average of bit accuracy probability increased by about 5.3~\%, compared with previous work.
Akshima, Siyao Guo, Qipeng Liu
We revisit the problem of finding $B$-block-long collisions in Merkle-Damgård Hash Functions in the auxiliary-input random oracle model, in which an attacker gets a piece of $S$-bit advice about the random oracle and makes $T$ oracle queries.
Akshima, Cash, Drucker and Wee (CRYPTO 2020), based on the work of Coretti, Dodis, Guo and Steinberger (EUROCRYPT 2018), showed a simple attack for $2\leq B\leq T$ (with respect to a random salt). The attack achieves advantage ${\Omega}(STB/2^n+T^2/2^n)$ where $n$ is the output length of the random oracle. They conjectured that this attack is optimal. However, this so-called STB conjecture was only proved for $B\approx T$ and $B=2$.
Very recently, Ghoshal and Komargodski (CRYPTO 22) confirmed STB conjecture for all constant values of $B$, and provided an ${O}(S^4TB^2/2^n+T^2/2^n)$ bound for all choices of $B$.
In this work, we prove an ${O}((STB/2^n)\cdot\max\{1,ST^2/2^n\}+ T^2/2^n)$ bound for every $2< B < T$. Our bound confirms the STB conjecture for $ST^2\leq 2^n$, and is optimal up to a factor of $S$ for $ST^2>2^n$ (note as $T^2$ is always at most $2^n$, otherwise finding a collision is trivial by the birthday attack). Our result subsumes all previous upper bounds for all ranges of parameters except for $B={O}(1)$ and $ST^2>2^n$.
We obtain our results by adopting and refining the technique of Chung, Guo, Liu, and Qian (FOCS 2020). Our approach yields more modular proofs and sheds light on how to bypass the limitations of prior techniques.
Along the way, we obtain a considerably simpler and illuminating proof for $B=2$, recovering the main result of Akshima, Cash, Drucker and Wee.
Very recently, Ghoshal and Komargodski (CRYPTO 22) confirmed STB conjecture for all constant values of $B$, and provided an ${O}(S^4TB^2/2^n+T^2/2^n)$ bound for all choices of $B$.
In this work, we prove an ${O}((STB/2^n)\cdot\max\{1,ST^2/2^n\}+ T^2/2^n)$ bound for every $2< B < T$. Our bound confirms the STB conjecture for $ST^2\leq 2^n$, and is optimal up to a factor of $S$ for $ST^2>2^n$ (note as $T^2$ is always at most $2^n$, otherwise finding a collision is trivial by the birthday attack). Our result subsumes all previous upper bounds for all ranges of parameters except for $B={O}(1)$ and $ST^2>2^n$.
We obtain our results by adopting and refining the technique of Chung, Guo, Liu, and Qian (FOCS 2020). Our approach yields more modular proofs and sheds light on how to bypass the limitations of prior techniques.
Along the way, we obtain a considerably simpler and illuminating proof for $B=2$, recovering the main result of Akshima, Cash, Drucker and Wee.
Prabhanjan Ananth, Fatih Kaleoglu, Xingjian Li, Qipeng Liu, Mark Zhandry
Unclonable encryption, first introduced by Broadbent and Lord (TQC'20), is a one-time encryption scheme with the following security guarantee: any non-local adversary (A, B, C) cannot simultaneously distinguish encryptions of two equal length messages. This notion is termed as unclonable indistinguishability. Prior works focused on achieving a weaker notion of unclonable encryption, where we required that any non-local adversary (A, B, C) cannot simultaneously recover the entire message m. Seemingly innocuous, understanding the feasibility of encryption schemes satisfying unclonable indistinguishability (even for 1-bit messages) has remained elusive.
We make progress towards establishing the feasibility of unclonable encryption.
- We show that encryption schemes satisfying unclonable indistinguishability exist unconditionally in the quantum random oracle model.
- Towards understanding the necessity of oracles, we present a negative result stipulating that a large class of encryption schemes cannot satisfy unclonable indistinguishability.
- Finally, we also establish the feasibility of another closely related primitive: copy-protection for single-bit output point functions. Prior works only established the feasibility of copy-protection for multi-bit output point functions or they achieved constant security error for single-bit output point functions.
We make progress towards establishing the feasibility of unclonable encryption.
- We show that encryption schemes satisfying unclonable indistinguishability exist unconditionally in the quantum random oracle model.
- Towards understanding the necessity of oracles, we present a negative result stipulating that a large class of encryption schemes cannot satisfy unclonable indistinguishability.
- Finally, we also establish the feasibility of another closely related primitive: copy-protection for single-bit output point functions. Prior works only established the feasibility of copy-protection for multi-bit output point functions or they achieved constant security error for single-bit output point functions.
Ilan Komargodski, Elaine Shi
Oblivious RAM (ORAM) is a machinery that protects any RAM from leaking information about its secret input by observing only the access pattern. It is known that every ORAM must incur a logarithmic overhead compared to the non-oblivious RAM. In fact, even the seemingly weaker notion of differential obliviousness, which intuitively ``protects'' a single access by guaranteeing that the observed access pattern for every two ``neighboring'' logical access sequences satisfy $(\epsilon,\delta)$-differential privacy, is subject to a logarithmic lower bound.
In this work, we show that any Turing machine computation can be generically compiled into a differentially oblivious one with only doubly logarithmic overhead. More precisely, given a Turing machine that makes $N$ transitions, the compiled Turing machine makes $O(N \cdot \log\log N)$ transitions in total and the physical head movements sequence satisfies $(\epsilon,\delta)$-differential privacy (for a constant $\epsilon$ and a negligible $\delta$). We additionally show that $\Omega(\log\log N)$ overhead is necessary in a natural range of parameters (and in the balls and bins model).
As a corollary, we show that there exist natural data structures such as stack and queues (supporting online operations) on $N$ elements for which there is a differentially oblivious implementation on a Turing machine incurring amortized $O(\log\log N)$ overhead per operation, while it is known that any oblivious implementation must consume $\Omega(\log N)$ operations unconditionally even on a RAM. Therefore, we obtain the first \emph{unconditional} separation between obliviousness and differential obliviousness in the most natural setting of parameters where $\epsilon$ is a constant and $\delta$ is negligible. Before this work, such a separation was only known in the balls and bins model. Note that the lower bound applies in the RAM model while our upper bound is in the Turing machine model, making our separation stronger.
In this work, we show that any Turing machine computation can be generically compiled into a differentially oblivious one with only doubly logarithmic overhead. More precisely, given a Turing machine that makes $N$ transitions, the compiled Turing machine makes $O(N \cdot \log\log N)$ transitions in total and the physical head movements sequence satisfies $(\epsilon,\delta)$-differential privacy (for a constant $\epsilon$ and a negligible $\delta$). We additionally show that $\Omega(\log\log N)$ overhead is necessary in a natural range of parameters (and in the balls and bins model).
As a corollary, we show that there exist natural data structures such as stack and queues (supporting online operations) on $N$ elements for which there is a differentially oblivious implementation on a Turing machine incurring amortized $O(\log\log N)$ overhead per operation, while it is known that any oblivious implementation must consume $\Omega(\log N)$ operations unconditionally even on a RAM. Therefore, we obtain the first \emph{unconditional} separation between obliviousness and differential obliviousness in the most natural setting of parameters where $\epsilon$ is a constant and $\delta$ is negligible. Before this work, such a separation was only known in the balls and bins model. Note that the lower bound applies in the RAM model while our upper bound is in the Turing machine model, making our separation stronger.
Jakob Feldtkeller, David Knichel, Pascal Sasdrich, Amir Moradi, Tim Güneysu
Physical characteristics of electronic devices, leaking secret and sensitive information to an adversary with physical access, pose a long-known threat to cryptographic hardware implementations. Among a variety of proposed countermeasures against such Side-Channel Analysis attacks, masking has emerged as a promising, but often costly, candidate. Furthermore, the manual realization of masked implementations has proven error-prone and often introduces flaws, possibly resulting in insecure circuits. In the context of automatic masking, a new line of research emerged, aiming to replace each physical gate with a secure gadget that fulfills well-defined properties, guaranteeing security when interconnected to a large circuit. Unfortunately, those gadgets introduce a significant amount of additional overhead into the design, in terms of area, latency, and randomness requirements.
In this work, we present a novel approach to reduce the demands for randomness in such gadget-composed circuits by reusing randomness across gadgets while maintaining security in the probing adversary model. To this end, we embedded the corresponding optimization passes into an Electronic Design Automation toolchain, able to construct, optimize, and implement masked circuits, starting from an unprotected design. As such, our security-aware optimization offers an additional building block for existing or new Electronic Design Automation frameworks, where security is considered a first-class design constraint
Lipeng Wan, Fangyu Zheng, Guang Fan, Rong Wei, Lili Gao, Jiankuo Dong, Jingqiang Lin, Yuewu Wang
Public-key cryptography (PKC), including conventional cryptosystems (e.g., RSA, ECC) and post-quantum cryptography, involves computation-intensive workloads. With noticing the extraordinary computing power of AI accelerators, in this paper, we further explore the feasibility to introduce AI accelerators into high-performance cryptographic computing. Since AI accelerators are dedicated to machine learning or neural networks, the biggest challenge is how to transform cryptographic workloads into their operations, while ensuring the correctness of the results and bringing convincing performance gains.
After investigating and analysing the workload of the commercial off-the-shelf AI accelerators, we utilize NVIDIA's AI accelerator, Tensor Core, to accelerate the polynomial multiplication, usually the most time-consuming part in lattice-based cryptography. A series of measures are taken, such as accommodating the matrix-multiply-and-add mode of Tensor Core and making a trade-off between precision and performance, to leverage Tensor Core as a high-performance NTT box performing NTT/INTT through CUDA C++ WMMA API. Meanwhile, we take CRYSTALS-Kyber, one of the NIST PQC 3rd round candidates, as a case study on RTX 3080 with the Ampere Tensor Core. The empirical results show that the defined NTT of polynomial vector ($n=256,k=4$) with our NTT box obtains a speedup of around 6.47x that of the state-of-the-art implementation on the same platform.
After investigating and analysing the workload of the commercial off-the-shelf AI accelerators, we utilize NVIDIA's AI accelerator, Tensor Core, to accelerate the polynomial multiplication, usually the most time-consuming part in lattice-based cryptography. A series of measures are taken, such as accommodating the matrix-multiply-and-add mode of Tensor Core and making a trade-off between precision and performance, to leverage Tensor Core as a high-performance NTT box performing NTT/INTT through CUDA C++ WMMA API. Meanwhile, we take CRYSTALS-Kyber, one of the NIST PQC 3rd round candidates, as a case study on RTX 3080 with the Ampere Tensor Core. The empirical results show that the defined NTT of polynomial vector ($n=256,k=4$) with our NTT box obtains a speedup of around 6.47x that of the state-of-the-art implementation on the same platform.
Gustavo Banegas, Valerie Gilchrist, Benjamin Smith
Many public-key cryptographic protocols, notably non-interactive key exchange (NIKE), require incoming public keys to be validated to mitigate some adaptive attacks. In CSIDH, an isogeny-based post-quantum NIKE, a key is deemed legitimate if the given Montgomery coefficient specifies a supersingular elliptic curve over the prime field. In this work, we survey the current supersingularity tests used for CSIDH key validation, and implement and measure two new alternative algorithms. Our implementation shows that we can determine supersingularity substantially faster, and using less memory, than the state-of-the-art.
Aurélien Greuet, Simon Montoya, Clémence Vermeersch
Modular polynomial multiplication is a core and costly operation of ideal lattice-based schemes. In the context of embedded devices, previous works transform the polynomial multiplication to an integer one using Kronecker substitution. Then thanks to this transformation, existing coprocessors which handle large-integer operations can be re-purposed to speed-up lattice-based cryptography. In a nutshell, the Kronecker substitution transforms by evaluation the polynomials to integers, multiplies it with an integer multiplication and gets back to a polynomial result using a radix conversion. The previous work focused on optimization of the integer multiplication using coprocessor instructions. In this work, we pursue the seminal research by optimizing the evaluation, radix conversion and the modular reductions modulo q with today's RSA/ECC coprocessor. In particular we show that with a RSA/ECC coprocessor that can compute addition/subtraction, (modular) multiplication, shift and logical AND on integers, we can compute the whole modular polynomial multiplication using coprocessor instructions. The efficiency of our modular polynomial multiplication depends on the component specification and on the cryptosystem parameters set. Hence, we assess our algorithm on a chip for several lattice-based schemes, which are finalists of the NIST standardization. Moreover, we compare our modular polynomial multiplication with other polynomial multiplication techniques.
Michael Rosenberg, Jacob White, Christina Garman, Ian Miers
Frequently, users on the web need to show that they are, for example, not a robot, old enough to access an age restricted video, or eligible to download an ebook from their local public library without being tracked. Anonymous credentials were developed to address these concerns. However, existing schemes do not handle the realities of deployment or the complexities of real world identity. Instead, they make (often incorrect) assumptions, e.g., that the local department of motor vehicles will issue sophisticated cryptographic tokens to show users are over 18. In reality, there are multiple trust sources for a given identity attribute, their credentials have distinctively different formats, and many, if not all, issuers are unwilling to adopt new protocols.
We present and build $\texttt{zk-creds}$, a protocol that uses general-purpose zero-knowledge proofs to 1) remove the need for credential issuers to hold signing keys: credentials can be issued via a transparency log, Byzantine system, or even a blockchain; 2) convert existing identity documents into anonymous credentials without modifying documents or coordinating with their issuing authority; 3) allow for flexible, composable, and complex identity statements over multiple credentials. Concretely, identity assertions using $\texttt{zk-creds}$ take less than 300ms in a real-world scenario of using a passport to anonymously access age-restricted videos.
We present and build $\texttt{zk-creds}$, a protocol that uses general-purpose zero-knowledge proofs to 1) remove the need for credential issuers to hold signing keys: credentials can be issued via a transparency log, Byzantine system, or even a blockchain; 2) convert existing identity documents into anonymous credentials without modifying documents or coordinating with their issuing authority; 3) allow for flexible, composable, and complex identity statements over multiple credentials. Concretely, identity assertions using $\texttt{zk-creds}$ take less than 300ms in a real-world scenario of using a passport to anonymously access age-restricted videos.