13753nam 22009495 450 99646619330331620200629191054.03-662-48797-710.1007/978-3-662-48797-6(CKB)4340000000001302(SSID)ssj0001584805(PQKBManifestationID)16265083(PQKBTitleCode)TC0001584805(PQKBWorkID)14863969(PQKB)10008181(DE-He213)978-3-662-48797-6(MiAaPQ)EBC6294819(MiAaPQ)EBC5594403(Au-PeEL)EBL5594403(OCoLC)932170944(PPN)19052944X(EXLCZ)99434000000000130220151126d2015 u| 0engurnn#008mamaatxtccrAdvances in Cryptology -- ASIACRYPT 2015[electronic resource] 21st International Conference on the Theory and Application of Cryptology and Information Security,Auckland, New Zealand, November 29 -- December 3, 2015, Proceedings, Part I /edited by Tetsu Iwata, Jung Hee Cheon1st ed. 2015.Berlin, Heidelberg :Springer Berlin Heidelberg :Imprint: Springer,2015.1 online resource (XXV, 810 p. 93 illus.)Security and Cryptology ;9452Bibliographic Level Mode of Issuance: Monograph3-662-48796-9 Includes bibliographical references and index.Intro -- Preface -- ASIACRYPT 2015 -- Invited Talks -- Structure-Preserving Cryptography -- Computer-Aided Cryptography:Status and Perspectives -- The Moral Character of Cryptographic Work -- Contents - Part I -- Contents - Part II -- Best Paper -- Improved Security Proofs in Lattice-Based Cryptography: Using the Rényi Divergence Rather Than the Statistical Distance -- 1 Introduction -- 2 Preliminaries -- 2.1 Lattices -- 2.2 The SIS and LWE Problems -- 2.3 The Rényi Divergence -- 2.4 RD Bounds -- 3 Application to Lattice-Based Signature Schemes -- 3.1 Sampling Discrete Gaussians and the BLISS Signature Scheme -- 3.2 GPV Signature Scheme -- 4 Rényi Divergence and Distinguishing Problems -- 4.1 Problems with Public Sampleability -- 4.2 Application to Dual-Regev Encryption -- 5 Application to LWE with Uniform Noise -- 6 Open Problems -- References -- Indistinguishability Obfuscation -- Multi-input Functional Encryption for Unbounded Arity Functions -- 1 Introduction -- 1.1 Our Results -- 1.2 Technical Overview -- 2 Preliminaries -- 2.1 Public-Coin Differing-Inputs Obfuscation -- 2.2 Non Interactive Proof Systems -- 2.3 Collision Resistent Hash Functions -- 3 Unbounded Arity Multi-input Functional Encryption -- 3.1 Syntax -- 3.2 Security Definition -- 4 A Construction from Public-Coin Differing-Inputs Obfuscation -- 5 Security Proof -- References -- Multi-party Key Exchange for Unbounded Parties from Indistinguishability Obfuscation -- 1 Introduction -- 1.1 Our Contributions -- 1.2 Technical Overview -- 1.3 Other Related Work -- 2 Preliminaries -- 2.1 Indistinguishability Obfuscation and PRFs -- 2.2 Somewhere Statistically Binding Hash -- 3 Definitions -- 4 Static Secure NIKE for Unbounded Parties -- 4.1 Construction -- 4.2 Security Game and Hybrids -- 4.3 Removing the Setup -- 5 ID-NIKE for Unbounded Parties -- 5.1 Construction.5.2 Security Game and Hybrids -- 6 Conclusion -- A NIKE: Proofs of Indistinguishability of the Hybrids -- References -- PRFs and Hashes -- Adaptively Secure Puncturable Pseudorandom Functions in the Standard Model -- 1 Introduction -- 2 Preliminaries -- 2.1 Assumptions -- 3 Constrained Pseudorandom Functions -- 3.1 Puncturable Pseudorandom Functions -- 4 Construction -- 4.1 Proof of Security -- 5 t-Puncturable PRFs -- 5.1 Construction -- 5.2 Proof of Security -- 6 Conclusion -- References -- Multilinear and Aggregate Pseudorandom Functions: New Constructions and Improved Security -- 1 Introduction -- 2 Definitions -- 3 Polynomial Linear Pseudorandomness Security -- 3.1 Intuition -- 3.2 Formal Security Notion and Theorem -- 4 Applications -- 4.1 Aggregate Pseudorandom Functions -- 4.2 Multilinear Pseudorandom Functions -- References -- New Realizations of Somewhere Statistically Binding Hashing and Positional Accumulators -- 1 Introduction -- 1.1 Our Results -- 2 Preliminaries -- 3 Two-to-One SSB Hash -- 3.1 Two-to-One SSB Hash from DDH -- 3.2 Two-to-One SSB Hash from DCR -- 3.3 SSB with Local Opening from Two-to-One SSB -- 4 SSB Hash from Lossy Functions -- 5 SSB from -hiding -- 5.1 RSA and -hiding Preliminaries -- 5.2 Conforming Function -- 5.3 Our -hiding SSB Construction -- 6 Positional Accumulators -- A Constructing a Conforming Function -- References -- Discrete Logarithms and Number Theory -- Computing Individual Discrete Logarithms Faster in `39`42`"613A``45`47`"603AGF(pn) with the NFS-DL Algorithm -- 1 Introduction -- 1.1 Cryptographic Interest -- 1.2 The Number Field Sieve Algorithm for DL in Finite Fields -- 1.3 Previous Work on Individual Discrete Logarithm -- 1.4 Our Contributions -- 1.5 Outline -- 2 Preliminaries -- 2.1 Polynomial Selection Methods -- 2.2 Norm Upper Bound in a Number Field.2.3 Joux--Lercier--Smart--Vercauteren Fraction Method -- 3 Asymptotic Complexity of Individual DL Computation -- 3.1 Asymptotic Complexity of Initialization or Booting Step -- 3.2 Running-Time of Special-q Descent -- 4 Computing a Preimage in the Number Field -- 4.1 Preimage Computation in the JLSV1 Case -- 4.2 Preimage Computation in the gJL and Conjugation Cases -- 5 Preimages of Smaller Norm with Quadratic Subfields -- 5.1 Smaller Preimage Degree -- 5.2 Smaller Preimage Norm -- 5.3 Summary of Results -- 6 Practical Examples -- 6.1 Examples for Small n and pn of 180 Decimal Digits (dd) -- 6.2 Experiments: Finding Boots for Fp4 of 120 dd -- 7 Conclusion -- References -- Multiple Discrete Logarithm Problems with Auxiliary Inputs -- 1 Introduction -- 2 Discrete Logarithm Problem and Related Problems -- 3 Multiple DLPwAI: Cheon's Algorithm -- 3.1 Reduction of DLPwAI to DLP in the Exponent Using Cheon's Algorithm -- 3.2 Algorithm for Multiple DLP in the Exponent -- 3.3 Solving Multiple DLPwAI Using Cheon's Algorithm -- 4 Multiple DLPwAI: Kim and Cheon's Algorithm -- 4.1 Description of Algorithm -- 4.2 Complexity Analysis -- 4.3 Explicit Choices of Polynomials for Efficient Algorithms in the Case Of d P 1 -- 5 Conclusion -- A A Failed Approach for MDLPwAI When d P+1 -- B Non-uniform Birthday Problem: Girls and Boys -- References -- Solving Linear Equations Modulo Unknown Divisors: Revisited -- 1 Introduction -- 1.1 Our Contributions -- 2 Preliminary -- 3 The First Type of Equations -- 3.1 Our Main Result -- 3.2 Analysis of Multi-power RSA -- 4 The Second Type of Equations -- 4.1 Our Main Result -- 4.2 Applications -- 5 The Third Type of Equations -- 5.1 Our Main Result -- 5.2 Common Prime RSA -- 6 Conclusion -- References -- FourQ: Four-Dimensional Decompositions on a Q-curve over the Mersenne Prime -- 1 Introduction -- 2 The Curve: FourQ.2.1 A Complete Twisted Edwards Curve -- 2.2 Where did this Curve Come From? -- 2.3 The Cryptographic Security of FourQ -- 3 The Endomorphisms and -- 3.1 Explicit Formulas for -- 3.2 Deriving Explicit Formulas for -- 3.3 Eigenvalues -- 3.4 Section Summary -- 4 Optimal Scalar Decompositions -- 4.1 Babai Rounding and Optimal Bases -- 4.2 Handling Round-Off Errors -- 4.3 All-Positive Multiscalars -- 5 The Scalar Multiplication -- 5.1 Recoding the Multiscalar -- 5.2 The Full Routine -- 6 Performance Analysis and Results -- 6.1 Operation Counts -- 6.2 Experimental Results -- References -- Signatures -- Efficient Fully Structure-Preserving Signatures for Large Messages -- 1 Introduction -- 1.1 Our Contribution -- 1.2 Related Work -- 2 Preliminaries -- 2.1 Bilinear Groups -- 2.2 Signature Schemes -- 2.3 Structure-Preserving Signature Schemes -- 3 Randomizable and Strongly Unforgeable Signatures -- 4 Structure-Preserving Combined Signature Scheme -- 5 Fully Structure-Preserving Combined Signature Scheme -- References -- A Provably Secure Group Signature Scheme from Code-Based Assumptions -- 1 Introduction -- 1.1 Background and Motivation -- 1.2 Our Contributions -- 1.3 Overview of Our Techniques -- 1.4 Related Works and Open Questions -- 2 Preliminaries -- 2.1 Background on Code-Based Cryptography -- 2.2 Group Signatures -- 3 The Underlying Zero-Knowledge Argument System -- 3.1 The Interactive Protocol -- 3.2 Analysis of the Protocol -- 4 Our Code-Based Group Signature Scheme -- 4.1 Description of the Scheme -- 4.2 Efficiency and Correctness -- 4.3 Anonymity -- 4.4 Traceability -- 5 Implementation Results -- References -- Type 2 Structure-Preserving Signature Schemes Revisited -- 1 Introduction -- 2 Asymmetric Bilinear Pairings -- 3 Strongly Unforgeable Structure-Preserving Signatures -- 3.1 Type 2 Strongly Unforgeable SPS [4].3.2 Type 3 Strongly Unforgeable SPS -- 3.3 Comparisons -- 4 Randomizable Structure-Preserving Signatures -- 4.1 Type 2 Randomizable SPS [4] -- 4.2 Type 3 Randomizable SPS -- 4.3 Comparisons -- 4.4 Strongly-Optimal Signatures -- 5 A Closer Look at Type 2 Schemes -- 5.1 Conversion from Type 2 to Type 3 -- 5.2 Impossibility of Single PPE in Verification -- 5.3 Separation -- 5.4 Type 2: A Designer's Artifact? -- 6 Concluding Remarks -- A Groth-Sahai Proofs -- A.1 DLIN-Based Proofs -- A.2 DDH-Based Proofs -- References -- Design Principles for HFEv- Based Multivariate Signature Schemes -- 1 Introduction -- 2 Multivariate Cryptography -- 3 The HFEv- Signature Scheme -- 3.1 QUARTZ -- 3.2 Performance -- 3.3 Security of HFEv- Based Schemes -- 4 Design Principles for HFEv- Based Signature Schemes -- 4.1 Can We Use HFE Polynomials of Low Degree D? -- 4.2 Is the Ratio Between a and v Important for the Security of the Scheme? -- 4.3 Is the Upper Bound on dreg Given by Eq.(12) Reasonably Tight? -- 4.4 Does it Help to Guess Some Variables Before Applying a Gröbner Basis Algorithm? -- 5 The New Multivariate Signature Scheme Gui -- 5.1 Signature Generation -- 5.2 Signature Verification -- 6 Implementation and Comparison -- 6.1 Arithmetics Over Finite Fields -- 6.2 Inverting the HFEv- Core -- 6.3 Experiments and Comparison -- 6.4 Platforms Without PCLMULQDQ -- 6.5 Grover's Algorithm and Potential Extension to Larger Fields -- 7 Conclusion and Future Work -- References -- Multiparty Computation I -- Oblivious Network RAM and Leveraging Parallelism to Achieve Obliviousness -- 1 Introduction -- 1.1 Practical Applications -- 1.2 Background: The PRAM Model -- 1.3 Results and Contributions -- 1.4 Technical Highlights -- 1.5 Related Work -- 2 Definitions -- 2.1 Background: Random Access Machines (RAM) -- 2.2 Network RAM (NRAM) -- 2.3 Oblivious Network RAM (O-NRAM).2.4 Notion of Simulation.The two-volume set LNCS 9452 and 9453 constitutes the refereed proceedings of the 21st International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2015, held in Auckland, New Zealand, in November/December 2015. The 64 revised full papers and 3 invited talks presented were carefully selected from 251 submissions. They are organized in topical sections on indistinguishability obfuscation; PRFs and hashes; discrete logarithms and number theory; signatures; multiparty computation; public key encryption; ABE and IBE; zero-knowledge; attacks on ASASA; number field sieve; hashes and MACs; symmetric encryption; foundations; side-channel attacks; design of block ciphers; authenticated encryption; symmetric analysis; cryptanalysis; privacy and lattices.Security and Cryptology ;9452Data encryption (Computer science)Computer securityCoding theoryInformation theoryManagement information systemsComputer scienceComputersComputer science—MathematicsCryptologyhttps://scigraph.springernature.com/ontologies/product-market-codes/I28020Systems and Data Securityhttps://scigraph.springernature.com/ontologies/product-market-codes/I28060Coding and Information Theoryhttps://scigraph.springernature.com/ontologies/product-market-codes/I15041Management of Computing and Information Systemshttps://scigraph.springernature.com/ontologies/product-market-codes/I24067Theory of Computationhttps://scigraph.springernature.com/ontologies/product-market-codes/I16005Mathematics of Computinghttps://scigraph.springernature.com/ontologies/product-market-codes/I17001Data encryption (Computer science).Computer security.Coding theory.Information theory.Management information systems.Computer science.Computers.Computer science—Mathematics.Cryptology.Systems and Data Security.Coding and Information Theory.Management of Computing and Information Systems.Theory of Computation.Mathematics of Computing.005.82Iwata Tetsuedthttp://id.loc.gov/vocabulary/relators/edtCheon Jung Heeedthttp://id.loc.gov/vocabulary/relators/edtMiAaPQMiAaPQMiAaPQBOOK996466193303316Advances in Cryptology – ASIACRYPT 20152593525UNISA