Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben

2018 | Buch

Block Cipher Invariants as Eigenvectors of Correlation Matrices Kapitel lesen Erstes Kapitel lesen

Advances in Cryptology – ASIACRYPT 2018

24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2–6, 2018, Proceedings, Part I

herausgegeben von: Thomas Peyrin, Steven Galbraith

Verlag: Springer International Publishing

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

The three-volume set of LNCS 11272, 11273, and 11274 constitutes the refereed proceedings of the 24th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2018, held in Brisbane, Australia, in December 2018.

The 65 revised full papers were carefully selected from 234 submissions. They are organized in topical sections on Post-Quantum Cryptanalysis; Encrypted Storage; Symmetric-Key Constructions; Lattice Cryptography; Quantum Symmetric Cryptanalysis; Zero-Knowledge; Public Key and Identity-Based Encryption; Side-Channels; Signatures; Leakage-Resilient Cryptography; Functional/Inner Product/Predicate Encryption; Multi-party Computation; ORQM; Real World Protocols; Secret Sharing; Isogeny Cryptography; and Foundations.

Inhaltsverzeichnis

Frontmatter

Asiacrypt 2018 Best Paper

Frontmatter
Block Cipher Invariants as Eigenvectors of Correlation Matrices
Abstract
A new approach to invariant subspaces and nonlinear invariants is developed. This results in both theoretical insights and practical attacks on block ciphers. It is shown that, with minor modifications to some of the round constants, Midori-64 has a nonlinear invariant with \(2^{96}\) corresponding weak keys. Furthermore, this invariant corresponds to a linear hull with maximal correlation. By combining the new invariant with integral cryptanalysis, a practical key-recovery attack on 10 rounds of unmodified Midori-64 is obtained. The attack works for \(2^{96}\) weak keys and irrespective of the choice of round constants. The data complexity is \(1.25 \cdot 2^{21}\) chosen plaintexts and the computational cost is dominated by \(2^{56}\) block cipher calls. Finally, it is shown that similar techniques lead to a practical key-recovery attack on MANTIS-4. The full key is recovered using 640 chosen plaintexts and the attack requires about \(2^{56}\) block cipher calls.
Tim Beyne

Post-Quantum Cryptanalysis

Frontmatter
Practical Attacks Against the Walnut Digital Signature Scheme
Abstract
Recently, NIST started the process of standardizing quantum-resistant public-key cryptographic algorithms. WalnutDSA, the subject of this paper, is one of the 20 proposed signature schemes that are being considered for standardization. Walnut relies on a one-way function called E-Multiplication, which has a rich algebraic structure. This paper shows that this structure can be exploited to launch several practical attacks against the Walnut cryptosystem. The attacks work very well in practice; it is possible to forge signatures and compute equivalent secret keys for the 128-bit and 256-bit security parameters submitted to NIST in less than a second and in less than a minute respectively.
Ward Beullens, Simon R. Blackburn
Two Attacks on Rank Metric Code-Based Schemes: RankSign and an IBE Scheme
Abstract
RankSign [30] is a code-based signature scheme proposed to the NIST competition for quantum-safe cryptography [5] and, moreover, is a fundamental building block of a new Identity-Based-Encryption (IBE) [26]. This signature scheme is based on the rank metric and enjoys remarkably small key sizes, about 10KBytes for an intended level of security of 128 bits. Unfortunately we will show that all the parameters proposed for this scheme in [5] can be broken by an algebraic attack that exploits the fact that the augmented LRPC codes used in this scheme have very low weight codewords. Therefore, without RankSign the IBE cannot be instantiated at this time. As a second contribution we will show that the problem is deeper than finding a new signature in rank-based cryptography, we also found an attack on the generic problem upon which its security reduction relies. However, contrarily to the RankSign scheme, it seems that the parameters of the IBE scheme could be chosen in order to avoid our attack. Finally, we have also shown that if one replaces the rank metric in the [26] IBE scheme by the Hamming metric, then a devastating attack can be found.
Thomas Debris-Alazard, Jean-Pierre Tillich
An Efficient Structural Attack on NIST Submission DAGS
Abstract
We present an efficient key recovery attack on code based encryption schemes using some quasi-dyadic alternant codes with extension degree 2. This attack permits to break the proposal DAGS recently submitted to NIST.
Élise Barelli, Alain Couvreur

Encrypted Storage

Frontmatter
Pattern Matching on Encrypted Streams
Abstract
Pattern matching is essential in applications such as deep-packet inspection (DPI), searching on genomic data, or analyzing medical data. A simple task to do on plaintext data, pattern matching is much harder to do when the privacy of the data must be preserved. Existent solutions involve searchable encryption mechanisms with at least one of these three drawbacks: requiring an exhaustive (and static) list of keywords to be prepared before the data is encrypted (like in symmetric searchable encryption); requiring tokenization, i.e., breaking up the data to search into substrings and encrypting them separately (e.g., like BlindBox); relying on symmetric-key cryptography, thus implying a token-regeneration step for each encrypted-data source (e.g., user). Such approaches are ill-suited for pattern-matching with evolving patterns (e.g., updating virus signatures), variable searchword lengths, or when a single entity must filter ciphertexts from multiple parties.
In this work, we introduce Searchable Encryption with Shiftable Trapdoors (SEST): a new primitive that allows for pattern matching with universal tokens (usable by all entities), in which keywords of arbitrary lengths can be matched to arbitrary ciphertexts. Our solution uses public-key encryption and bilinear pairings.
In addition, very minor modifications to our solution enable it to take into account regular expressions, such as fully- or partly-unknown characters in a keyword (wildcards and interval/subset searches). Our trapdoor size is at most linear in the keyword length (and independent of the plaintext size), and we prove that the leakage to the searcher is only the trivial one: since the searcher learns whether the pattern occurs and where, it can distinguish based on different search results of a single trapdoor on two different plaintexts.
To better show the usability of our scheme, we implemented it to run DPI on all the SNORT rules. We show that even for very large plaintexts, our encryption algorithm scales well. The pattern-matching algorithm is slower, but extremely parallelizable, and it can thus be run even on very large data. Although our proofs use a (marginally) interactive assumption, we argue that this is a relatively small price to pay for the flexibility and privacy that we are able to attain.
Nicolas Desmoulins, Pierre-Alain Fouque, Cristina Onete, Olivier Sanders
SQL on Structurally-Encrypted Databases
Abstract
We show how to encrypt a relational database in such a way that it can efficiently support a large class of SQL queries. Our construction is based solely on structured encryption (STE) and does not make use of any property-preserving encryption (PPE) schemes such as deterministic and order-preserving encryption. As such, our approach leaks considerably less than PPE-based solutions which have recently been shown to reveal a lot of information in certain settings (Naveed et al., CCS ’15). Our construction is efficient and—under some conditions on the database and queries—can have asymptotically-optimal query complexity. We also show how to extend our solution to be dynamic while maintaining the scheme’s optimal query complexity.
Seny Kamara, Tarik Moataz
Parameter-Hiding Order Revealing Encryption
Abstract
Order-revealing encryption (ORE) is a primitive for outsourcing encrypted databases which allows for efficiently performing range queries over encrypted data. Unfortunately, a series of works, starting with Naveed et al. (CCS 2015), have shown that when the adversary has a good estimate of the distribution of the data, ORE provides little protection. In this work, we consider the case that the database entries are drawn identically and independently from a distribution of known shape, but for which the mean and variance are not (and thus the attacks of Naveed et al. do not apply). We define a new notion of security for ORE, called parameter-hiding ORE, which maintains the secrecy of these parameters. We give a construction of ORE satisfying our new definition from bilinear maps.
David Cash, Feng-Hao Liu, Adam O’Neill, Mark Zhandry, Cong Zhang

Symmetric-Key Constructions

Frontmatter
Revisiting Key-Alternating Feistel Ciphers for Shorter Keys and Multi-user Security
Abstract
Key-Alternating Feistel (KAF) ciphers, a.k.a. Feistel-2 models, refer to Feistel networks with round functions of the form \(F_i(k_i\oplus x_i)\), where \(k_i\) is the (secret) round-key and \(F_i\) is a public random function. This model roughly captures the structures of many famous Feistel ciphers, and the most prominent instance is DES.
Existing provable security results on KAF assumed independent round-keys and round functions (ASIACRYPT 2004 & FSE 2014). In this paper, we investigate how to achieve security under simpler and more realistic assumptions: with round-keys derived from a short main-key, and hopefully with identical round functions.
For birthday-type security, we consider 4-round KAF, investigate the minimal conditions on the way to derive the four round-keys, and prove that when such adequately derived keys and the same round function are used, the 4-round KAF is secure up to \(2^{n/2}\) queries.
For beyond-birthday security, we focus on 6-round KAF. We prove that when the adjacent round-keys are independent, and independent round-functions are used, the 6 round KAF is secure up to \(2^{2n/3}\) queries. To our knowledge, this is the first beyond-birthday security result for KAF without assuming completely independent round-keys.
Our results hold in the multi-user setting as well, constituting the first non-trivial multi-user provable security results on Feistel ciphers. We finally demonstrate applications of our results on designing key-schedules and instantiating keyed sponge constructions.
Chun Guo, Lei Wang
Short Variable Length Domain Extenders with Beyond Birthday Bound Security
Abstract
Length doublers are cryptographic functions that transform an n-bit cryptographic primitive into an efficient and secure cipher that length-preservingly encrypts strings of length in \([n,2n-1]\). All currently known constructions are only proven secure up to the birthday bound, and for all but one construction this bound is known to be tight. We consider the remaining candidate, \(\mathrm {LDT}\) by Chen et al. (ToSC 2017(3)), and prove that it achieves beyond the birthday bound security for the domain [n, 3n / 2). We generalize the construction to multiple rounds and demonstrate that by adding one more encryption layer to \(\mathrm {LDT} \), beyond the birthday bound security can be achieved for all strings of length in \([n,2n-1]\): security up to around \(2^{2n/3}\) for the encryption of strings close to n and security up to around \(2^{n}\) for strings of length close to 2n. The security analysis of both schemes is performed in a modular manner through the introduction and analysis of a new concept called “harmonic permutation primitives.”
Yu Long Chen, Bart Mennink, Mridul Nandi
Building Quantum-One-Way Functions from Block Ciphers: Davies-Meyer and Merkle-Damgård Constructions
Abstract
We present hash functions that are almost optimally one-way in the quantum setting. Our hash functions are based on the Merkle-Damgård construction iterating a Davies-Meyer compression function, which is built from a block cipher. The quantum setting that we use is a natural extention of the classical ideal cipher model. Recent work has revealed that symmetric-key schemes using a block cipher or a public permutation, such as CBC-MAC or the Even-Mansour cipher, can get completely broken with quantum superposition attacks, in polynomial time of the block size. Since many of the popular schemes are built from a block cipher or a permutation, the recent findings motivate us to study such schemes that are provably secure in the quantum setting. Unfortunately, no such schemes are known, unless one relies on certain algebraic assumptions. In this paper we present hash constructions that are provably one-way in the quantum setting without algebraic assumptions, solely based on the assumption that the underlying block cipher is ideal. To do this, we reduce one-wayness to a problem of finding a fixed point and then bound its success probability with a distinguishing advantage. We develop a generic tool that helps us prove indistinguishability of two quantum oracle distributions.
Akinori Hosoyamada, Kan Yasuda
Tweakable Block Ciphers Secure Beyond the Birthday Bound in the Ideal Cipher Model
Abstract
We propose a new construction of tweakable block ciphers from standard block ciphers. Our construction, dubbed \(\mathsf {XHX2}\), is the cascade of two independent \(\mathsf {XHX}\) block ciphers, so it makes two calls to the underlying block cipher using tweak-dependent keys. We prove the security of \(\mathsf {XHX2}\) up to \(\min \{2^{2(n+m)/3},2^{n+m/2}\}\) queries (ignoring logarithmic factors) in the ideal cipher model, when the block cipher operates on n-bit blocks using m-bit keys. The \(\mathsf {XHX2}\) tweakable block cipher is the first construction that achieves beyond-birthday-bound security with respect to the input size of the underlying block cipher in the ideal cipher model.
ByeongHak Lee, Jooyoung Lee
ZCZ – Achieving n-bit SPRP Security with a Minimal Number of Tweakable-Block-Cipher Calls
Abstract
Strong Pseudo-random Permutations (SPRPs) are important for various applications. In general, it is desirable to base an SPRP on a single-keyed primitive for minimizing the implementation costs. For constructions built on classical block ciphers, Nandi showed at ASIACRYPT’15 that at least two calls to the primitive per processed message block are required for SPRP security, assuming that all further operations are linear. The ongoing trend of using tweakable block ciphers as primitive has already led to MACs or encryption modes with high security and efficiency properties. Thus, three interesting research questions are hovering in the domain of SPRPs: (1) if and to which extent the bound of two calls per block can be reduced with a tweakable block cipher, (2) how concrete constructions could be realized, and (3) whether full n-bit security is achievable from primitives with n-bit state size.
The present work addresses all three questions. Inspired by Iwata et al.’s ZHash proposal at CRYPTO’17, we propose the ZCZ (ZHash-Counter-ZHash) construction, a single-key variable-input-length SPRP based on a single tweakable block cipher whose tweak length is at least its state size. ZCZ possesses close to optimal properties with regards to both performance and security: not only does it require only asymptotically \(3\ell /2\) calls to the primitive for \(\ell \)-block messages; we show that this figure is close to the minimum by an PRP distinguishing attack on any construction with tweak size of \(\tau = n\) bits and fewer than \((3\ell -1)/2\) calls to the same primitive. Moreover, it provides optimal n-bit security for a primitive with n-bit state and tweak size.
Ritam Bhaumik, Eik List, Mridul Nandi

Lattice-Based Cryptography

Frontmatter
Measuring, Simulating and Exploiting the Head Concavity Phenomenon in BKZ
Abstract
The Blockwise-Korkine-Zolotarev (BKZ) lattice reduction algorithm is central in cryptanalysis, in particular for lattice-based cryptography. A precise understanding of its practical behavior in terms of run-time and output quality is necessary for parameter selection in cryptographic design. As the provable worst-case bounds poorly reflect the practical behavior, cryptanalysts rely instead on the heuristic BKZ simulator of Chen and Nguyen (Asiacrypt’11). It fits better with practical experiments, but not entirely. In particular, it over-estimates the norm of the first few vectors in the output basis. Put differently, BKZ performs better than its Chen–Nguyen simulation.
In this work, we first report experiments providing more insight on this shorter-than-expected phenomenon. We then propose a refined BKZ simulator by taking the distribution of short vectors in random lattices into consideration. We report experiments suggesting that this refined simulator more accurately predicts the concrete behavior of BKZ. Furthermore, we design a new BKZ variant that exploits the shorter-than-expected phenomenon. For the same cost assigned to the underlying SVP-solver, the new BKZ variant produces bases of better quality. We further illustrate its potential impact by testing it on the SVP-120 instance of the Darmstadt lattice challenge.
Shi Bai, Damien Stehlé, Weiqiang Wen
Quantum Lattice Enumeration and Tweaking Discrete Pruning
Abstract
Enumeration is a fundamental lattice algorithm. We show how to speed up enumeration on a quantum computer, which affects the security estimates of several lattice-based submissions to NIST: if T is the number of operations of enumeration, our quantum enumeration runs in roughly \(\sqrt{T}\) operations. This applies to the two most efficient forms of enumeration known in the extreme pruning setting: cylinder pruning but also discrete pruning introduced at Eurocrypt ’17. Our results are based on recent quantum tree algorithms by Montanaro and Ambainis-Kokainis. The discrete pruning case requires a crucial tweak: we modify the preprocessing so that the running time can be rigorously proved to be essentially optimal, which was the main open problem in discrete pruning. We also introduce another tweak to solve the more general problem of finding close lattice vectors.
Yoshinori Aono, Phong Q. Nguyen, Yixin Shen
On the Hardness of the Computational Ring-LWR Problem and Its Applications
Abstract
In this paper, we propose a new assumption, the Computational Learning With Rounding over rings, which is inspired by the computational Diffie-Hellman problem. Assuming the hardness of R-LWE, we prove this problem is hard when the secret is small, uniform and invertible. From a theoretical point of view, we give examples of a key exchange scheme and a public key encryption scheme, and prove the worst-case hardness for both schemes with the help of a random oracle. Our result improves both speed, as a result of not requiring Gaussian secret or noise, and size, as a result of rounding. In practice, our result suggests that decisional R-LWR based schemes, such as Saber, Round2 and Lizard, which are among the most efficient solutions to the NIST post-quantum cryptography competition, stem from a provable secure design. There are no hardness results on the decisional R-LWR with polynomial modulus prior to this work, to the best of our knowledge.
Long Chen, Zhenfeng Zhang, Zhenfei Zhang
On the Statistical Leak of the GGH13 Multilinear Map and Some Variants
Abstract
At EUROCRYPT 2013, Garg, Gentry and Halevi proposed a candidate construction (later referred as GGH13) of cryptographic multilinear map (MMap). Despite weaknesses uncovered by Hu and Jia (EUROCRYPT 2016), this candidate is still used for designing obfuscators.
The naive version of the GGH13 scheme was deemed susceptible to averaging attacks, i.e., it could suffer from a statistical leak (yet no precise attack was described). A variant was therefore devised, but it remains heuristic. Recently, to obtain MMaps with low noise and modulus, two variants of this countermeasure were developed by Döttling et al. (EPRINT:2016/599).
In this work, we propose a systematic study of this statistical leakage for all these GGH13 variants. In particular, we confirm the weakness of the naive version of GGH13. We also show that, among the two variants proposed by Döttling et al., the so-called conservative method is not so effective: it leaks the same value as the unprotected method. Luckily, the leakage is more noisy than in the unprotected method, making the straightforward attack unsuccessful. Additionally, we note that all the other methods also leak values correlated with secrets.
As a conclusion, we propose yet another countermeasure, for which this leakage is made unrelated to all secrets. On our way, we also make explicit and tighten the hidden exponents in the size of the parameters, as an effort to assess and improve the efficiency of MMaps.
Léo Ducas, Alice Pellet-Mary
LWE Without Modular Reduction and Improved Side-Channel Attacks Against BLISS
Abstract
This paper is devoted to analyzing the variant of Regev’s learning with errors (LWE) problem in which modular reduction is omitted: namely, the problem (ILWE) of recovering a vector \(\mathbf {s}\in \mathbb {Z}^n\) given polynomially many samples of the form \((\mathbf {a},\langle \mathbf {a},\mathbf {s}\rangle + e)\in \mathbb {Z}^{n+1}\) where \(\mathbf { a}\) and e follow fixed distributions. Unsurprisingly, this problem is much easier than LWE: under mild conditions on the distributions, we show that the problem can be solved efficiently as long as the variance of e is not superpolynomially larger than that of \(\mathbf { a}\). We also provide almost tight bounds on the number of samples needed to recover \(\mathbf {s}\).
Our interest in studying this problem stems from the side-channel attack against the BLISS lattice-based signature scheme described by Espitau et al. at CCS 2017. The attack targets a quadratic function of the secret that leaks in the rejection sampling step of BLISS. The same part of the algorithm also suffers from a linear leakage, but the authors claimed that this leakage could not be exploited due to signature compression: the linear system arising from it turns out to be noisy, and hence key recovery amounts to solving a high-dimensional problem analogous to LWE, which seemed infeasible. However, this noisy linear algebra problem does not involve any modular reduction: it is essentially an instance of ILWE, and can therefore be solved efficiently using our techniques. This allows us to obtain an improved side-channel attack on BLISS, which applies to 100% of secret keys (as opposed to \({\approx }7\%\) in the CCS paper), and is also considerably faster.
Jonathan Bootle, Claire Delaplace, Thomas Espitau, Pierre-Alain Fouque, Mehdi Tibouchi

Quantum Symmetric Cryptanalysis

Frontmatter
Quantum Algorithms for the -xor Problem
Abstract
The \(k\)-xor (or generalized birthday) problem is a widely studied question with many applications in cryptography. It aims at finding k elements of n bits, drawn at random, such that the xor of all of them is 0. The algorithms proposed by Wagner more than fifteen years ago remain the best known classical algorithms for solving them, when disregarding logarithmic factors.
In this paper we study these problems in the quantum setting, when considering that the elements are created by querying a random function (or k random functions) \(H~: \{0,1\}^n \rightarrow \{0,1\}^n\). We consider two scenarios: in one we are able to use a limited amount of quantum memory (i.e. a number O(n) of qubits, the same as the one needed by Grover’s search algorithm), and in the other we consider that the algorithm can use an exponential amount of qubits. Our newly proposed algorithms are of general interest. In both settings, they provide the best known quantum time complexities.
In particular, we are able to considerately improve the \(3\)-xor algorithm: with limited qubits, we reach a complexity considerably better than what is currently possible for quantum collision search. Furthermore, when having access to exponential amounts of quantum memory, we can take this complexity below \(O(2^{n/3})\), the well-known lower bound of quantum collision search, clearly improving the best known quantum time complexity also in this setting.
We illustrate the importance of these results with some cryptographic applications.
Lorenzo Grassi, María Naya-Plasencia, André Schrottenloher
Hidden Shift Quantum Cryptanalysis and Implications
Abstract
At Eurocrypt 2017 a tweak to counter Simon’s quantum attack was proposed: replace the common bitwise addition with other operations, as a modular addition. The starting point of our paper is a follow up of these previous results:
First, we have developed new algorithms that improves and generalizes Kuperberg’s algorithm for the hidden shift problem, which is the algorithm that applies instead of Simon when considering modular additions. Thanks to our improved algorithm, we have been able to build a quantum attack in the superposition model on Poly1305, proposed at FSE 2005, widely used and claimed to be quantumly secure. We also answer an open problem by analyzing the effect of the tweak to the FX construction.
We have also generalized the algorithm. We propose for the first time a quantum algorithm for solving the hidden problem with parallel modular additions, with a complexity that matches both Simon and Kuperberg in its extremes.
In order to verify our theoretical analysis, and to get concrete estimates of the cost of the algorithms, we have simulated them, and were able to validate our estimated complexities.
Finally, we analyze the security of some classical symmetric constructions with concrete parameters, to evaluate the impact and practicality of the proposed tweak. We concluded that the tweak does not seem to be efficient.
Xavier Bonnetain, María Naya-Plasencia

Zero-Knowledge

Frontmatter
Arya: Nearly Linear-Time Zero-Knowledge Proofs for Correct Program Execution
Abstract
There have been tremendous advances in reducing interaction, communication and verification time in zero-knowledge proofs but it remains an important challenge to make the prover efficient. We construct the first zero-knowledge proof of knowledge for the correct execution of a program on public and private inputs where the prover computation is nearly linear time. This saves a polylogarithmic factor in asymptotic performance compared to current state of the art proof systems.
We use the TinyRAM model to capture general purpose processor computation. An instance consists of a TinyRAM program and public inputs. The witness consists of additional private inputs to the program. The prover can use our proof system to convince the verifier that the program terminates with the intended answer within given time and memory bounds. Our proof system has perfect completeness, statistical special honest verifier zero-knowledge, and computational knowledge soundness assuming linear-time computable collision-resistant hash functions exist. The main advantage of our new proof system is asymptotically efficient prover computation. The prover’s running time is only a superconstant factor larger than the program’s running time in an apples-to-apples comparison where the prover uses the same TinyRAM model. Our proof system is also efficient on the other performance parameters; the verifier’s running time and the communication are sublinear in the execution time of the program and we only use a log-logarithmic number of rounds.
Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune Jakobsen, Mary Maller
Improved (Almost) Tightly-Secure Simulation-Sound QA-NIZK with Applications
Abstract
We construct the first (almost) tightly-secure unbounded-simulation-sound quasi-adaptive non-interactive zero-knowledge arguments (USS-QA-NIZK) for linear-subspace languages with compact (number of group elements independent of the security parameter) common reference string (CRS) and compact proofs under standard assumptions in bilinear-pairings groups. In particular, under the SXDH assumption, the USS-QA-NIZK proof size is only seventeen group elements with a factor \(O(\log {Q})\) loss in security reduction to SXDH. The USS-QA-NIZK primitive has many applications, including structure-preserving signatures (SPS), CCA2-secure publicly-verifiable public-key encryption (PKE), which in turn have applications to CCA-anonymous group signatures, blind signatures and unbounded simulation-sound Groth-Sahai NIZK proofs. We show that the almost tight security of our USS-QA-NIZK translates into constructions of all of the above applications with (almost) tight-security to standard assumptions such as SXDH and, more generally, \(\mathcal{D}_k\)-MDDH. Thus, we get the first publicly-verifiable (almost) tightly-secure multi-user/multi-challenge CCA2-secure PKE with practical efficiency under standard bilinear assumptions. Our (almost) tight SPS construction is also improved in the signature size over previously known constructions.
Masayuki Abe, Charanjit S. Jutla, Miyako Ohkubo, Arnab Roy
Backmatter
Metadaten
Titel
Advances in Cryptology – ASIACRYPT 2018
herausgegeben von
Thomas Peyrin
Steven Galbraith
Copyright-Jahr
2018
Electronic ISBN
978-3-030-03326-2
Print ISBN
978-3-030-03325-5
DOI
https://doi.org/10.1007/978-3-030-03326-2

Premium Partner

    Bildnachweise