Theory of Cryptography: 16th International Conference, TCC 2018, Panaji, India, November 11–14, 2018, Proceedings, Part I (Lecture Notes in Computer Science, 11239)

The two-volume set of LNCS 11239 and LNCS 11240 constitutes the revised proceedings of the 16th International Conference on Theory of Cryptography, TCC 2018, held in Panaji, India, in November 2018. The total of 50 revised full papers presented in the proceedings were carefully reviewed and selected from 168 submissions. The Theory of Cryptography Conference deals with the paradigms, approaches, and techniques used to conceptualize natural cryptographic problems and provide algorithmic solutions to them and much more. Front Matter ....Pages I-XVII Front Matter ....Pages 1-1 Provable Time-Memory Trade-Offs: Symmetric Cryptography Against Memory-Bounded Adversaries (Stefano Tessaro, Aishwarya Thiruvengadam)....Pages 3-32 Static-Memory-Hard Functions, and Modeling the Cost of Space vs. Time (Thaddeus Dryja, Quanquan C. Liu, Sunoo Park)....Pages 33-66 No-signaling Linear PCPs (Susumu Kiyoshima)....Pages 67-97 On Basing Search SIVP on NP-Hardness (Tianren Liu)....Pages 98-119 Front Matter ....Pages 121-121 Two-Round MPC: Information-Theoretic and Black-Box (Sanjam Garg, Yuval Ishai, Akshayaram Srinivasan)....Pages 123-151 Perfect Secure Computation in Two Rounds (Benny Applebaum, Zvika Brakerski, Rotem Tsabary)....Pages 152-174 Two-Round Adaptively Secure Multiparty Computation from Standard Assumptions (Fabrice Benhamouda, Huijia Lin, Antigoni Polychroniadou, Muthuramakrishnan Venkitasubramaniam)....Pages 175-205 Front Matter ....Pages 207-207 One-Message Zero Knowledge and Non-malleable Commitments (Nir Bitansky, Huijia Lin)....Pages 209-234 Smooth NIZK Arguments (Charanjit S. Jutla, Arnab Roy)....Pages 235-262 Round-Optimal Fully Black-Box Zero-Knowledge Arguments from One-Way Permutations (Carmit Hazay, Muthuramakrishnan Venkitasubramaniam)....Pages 263-285 Round Optimal Black-Box “Commit-and-Prove” (Dakshita Khurana, Rafail Ostrovsky, Akshayaram Srinivasan)....Pages 286-313 Front Matter ....Pages 315-315 On the Power of Amortization in Secret Sharing: d-Uniform Secret Sharing and CDS with Constant Information Rate (Benny Applebaum, Barak Arkis)....Pages 317-344 Information-Theoretic Secret-Key Agreement: The Asymptotically Tight Relation Between the Secret-Key Rate and the Channel Quality Ratio (Daniel Jost, Ueli Maurer, João L. Ribeiro)....Pages 345-369 Information-Theoretic Broadcast with Dishonest Majority for Long Messages (Wutichai Chongchitmate, Rafail Ostrovsky)....Pages 370-388 Oblivious Transfer in Incomplete Networks (Varun Narayanan, Vinod M. Prabahakaran)....Pages 389-418 Front Matter ....Pages 419-419 Injective Trapdoor Functions via Derandomization: How Strong is Rudich’s Black-Box Barrier? (Lior Rotem, Gil Segev)....Pages 421-447 Enhancements are Blackbox Non-trivial: Impossibility of Enhanced Trapdoor Permutations from Standard Trapdoor Permutations (Mohammad Hajiabadi)....Pages 448-475 Certifying Trapdoor Permutations, Revisited (Ran Canetti, Amit Lichtenberg)....Pages 476-506 On the Security Loss of Unique Signatures (Andrew Morgan, Rafael Pass)....Pages 507-536 Front Matter ....Pages 537-537 On the Complexity of Fair Coin Flipping (Iftach Haitner, Nikolaos Makriyannis, Eran Omri)....Pages 539-562 Game Theoretic Notions of Fairness in Multi-party Coin Toss (Kai-Min Chung, Yue Guo, Wei-Kai Lin, Rafael Pass, Elaine Shi)....Pages 563-596 Achieving Fair Treatment in Algorithmic Classification (Andrew Morgan, Rafael Pass)....Pages 597-625 Front Matter ....Pages 627-627 Upgrading to Functional Encryption (Saikrishna Badrinarayanan, Dakshita Khurana, Amit Sahai, Brent Waters)....Pages 629-658 Impossibility of Simulation Secure Functional Encryption Even with Random Oracles (Shashank Agrawal, Venkata Koppula, Brent Waters)....Pages 659-688 Registration-Based Encryption: Removing Private-Key Generator from IBE (Sanjam Garg, Mohammad Hajiabadi, Mohammad Mahmoody, Ahmadreza Rahimi)....Pages 689-718 Back Matter ....Pages 719-720