Computer Science News
New spin-out to make e-voting more secure, accessible and trustworthy
Researchers from the Systems and Security theme, Department of Computer Science have created a new spin-out company, SEEV Technologies Ltd, to build end-to-end (E2E) verifiable e-voting systems for future elections. An E2E verifiable voting system allows every voter to verify that their vote is properly cast-as-intended, recorded-as-cast and tallied-as-recorded while preserving the voter's privacy. SEEV (self-enforcing e-voting) is a new paradigm of E2E voting technology that enables voters to fully verify the tallying integrity of an election without needing any trustworthy tallying authority, hence the system is "self-enforcing".
This joint spin-out from the University of Warwick and Newcastle University is built on an ERC-funded starting grant ("Self-Enforcing E-Voting System: Trustworthy Election in Presence of Corrupt Authorities", No. 306994, PI: Professor Feng Hao) initially hosted at Newcastle University and later transferred to the University of Warwick. The company is co-founded by Professor Feng Hao and Dr Siamak Shandahshti (co-inventors), and led by Dr Stewart Hefferman (CEO). SEEV has been prototyped and successfully tested in several trials in the past, supported by an ERC Proof of Concept grant (No. 677124), a Royal Society International collaboration award (CA\R1\180226), and an Innovate UK Cybersecurity Academic Startup Accelerator Programme (CASAP). SEEV Technologies Ltd has received seed funding from Oxford-based Global Initiative to build SEEV systems for real-world elections.
A University of Warwick press release is here.
5 papers accepted to FOCS 2023
Five papers from the Theory and Foundations (FoCS) Research Group and the Centre for Discrete Mathematics and its Applications (DIMAP) have been accepted to the 64th IEEE Symposium on Foundations of Computer Science (FOCS 2023), the IEEE flagship conference in theoretical computer science that will be held on November 6 - 9, 2023 in Santa Cruz, California, USA:
- "Chasing positive bodies" by Sayan Bhattacharya, Niv Buchbinder, Roie Levin, and Thatchaphol Saranurak.
- "Dynamic (1+epsilon)-approximate matching size in truly sublinear update time" by Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak.
- "Polynomial-time pseudodeterministic construction of primes" by Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, and Rahul Santhanam.
- "Approximating edit distance in the fully dynamic model" by Tomasz Kociumaka, Anish Mukherjee, and Barna Saha.
- "Traversing combinatorial 0/1-polytopes via optimization" by Arturo Merino and Torsten Mütze.
Best Paper Award and 5 papers at the 50th ICALP conference
Henry Sinclair-Banks, a PhD student in the the Theory and Foundations (FoCS) Research Group and the Centre for Discrete Mathematics and its Applications (DIMAP), has won a Best Paper Award at ICALP 2023, the 50th EATCS International Colloquium on Automata, Languages and Programming. ICALP is the main conference and annual meeting of the European Association for Theoretical Computer Science (EATCS).
Henry's paper, co-authored with researchers from Germany and Poland: Marvin Künnemann, Filip Mazowiecki, Lia Schütze, and Karol Węgrzycki, addresses the coverability problem in vector addition systems (VASS), a well-known model of concurrent systems. Coverability is an algorithmic problem for the verification of "safety properties": whether the system always avoids a set of bad states. Henry and his co-authors determine how much time is required to solve this problem in the worst case. They develop an algorithm that improves upon the state of the art that has stood for forty years. They also prove that, in several settings, it is impossible to decide coverability substantially faster, unless there is also a faster algorithm for a classic problem such as Boolean satisfiability (SAT) and finding cycles of fixed length in graphs.
- Michael Benedikt, Dmitry Chistikov, and Alessio Mansutti, "The complexity of Presburger arithmetic with power or powers",
- Sam Coy, Artur Czumaj, Peter Davies, and Gopinath Mishra, "Optimal (degree+1)-coloring in congested clique",
- Charilaos Efthymiou and Weiming Feng, "On the mixing time of Glauber dynamics for the hard-core and related models on G(n,d/n)",
- Marvin Künnemann, Filip Mazowiecki, Lia Schütze, Henry Sinclair-Banks, and Karol Węgrzycki, "Coverability in VASS revisited: Improving Rackoff's bound to obtain conditional optimality",
- Konstantinos Zampetakis and Charilaos Efthymiou, "Broadcasting with random matrices".
This July's ICALP will be the 50th edition of the conference.
Spying on the Spy: Security Analysis of Hidden Cameras
When you purchase an IP-based spy (hidden) camera for surveillance, are you aware that others may be spying on what you are watching? Recent research by Samuel Herodotou in the Department of Computer Science, Warwick, as part of his third-year undergraduate dissertation project under the supervision of Professor Feng Hao, has revealed a wide range of vulnerabilities of a generic camera module that has been used in many best-selling hidden cameras. Exploiting these vulnerabilities, an attacker may capture your hidden camera's video/audio streams from anywhere in the world, and furthermore, take complete control of the camera as a bot to attack other devices in your home network. To launch the attack, all the attacker needs to know is merely your hidden camera’s serial number. It is estimated that these vulnerabilities affect millions of hidden cameras, mostly sold in America, Europe and Asia. The (insecure) peer-to-peer network that is used by the affected cameras is also being used by 50 million IoT devices as a general communication platform. Hence, many millions of other IoT devices may also be affected. Researchers have responsibly disclosed findings to the manufacturers, and a CVE has already been assigned. Samuel will present this research work at the 17th International Conference on Network and System Security (Canterbury, UK, 14-16 August 2023). More details can be found in the paper.
5+ papers accepted to STOC 2023
Several papers from the Theory and Foundations (FoCS) Research Group and the Centre for Discrete Mathematics and its Applications (DIMAP) have been accepted to the 55th ACM SIGACT Symposium on Theory of Computing (STOC 2023), the ACM flagship conference in theoretical computer science that will be held on June 20-23, 2023 in Orlando, Florida, USA:
- "Kneser graphs are Hamiltonian" by Arturo Merino, Torsten Mütze, and Namrata.
- "A duality between one-way functions and average-case symmetry of information" by Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, and Igor C. Oliveira.
- "Unprovability of strong complexity lower bounds in bounded arithmetic" by Jiatu Li and Igor C. Oliveira.
- "Sublinear algorithms for (1.5+ϵ)-approximate matching" by Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak.
- "Towards the Erdős-Gallai cycle decomposition conjecture" by Matija Bucic and Richard Montgomery.
Further, there are two more accepted papers autored by Shuichi Hirahara, who was affiliated with the department and the FoCS group during the submission time, in Autumn 2022:
- "Capturing one-way functions via NP-hardness of meta-complexity" by Shuichi Hirahara.
- "Hardness self-amplification: Simplified, optimized, and unified" by Shuichi Hirahara and Nobutaka Shimizu.
Prof. Adi Shamir receives Honorary Doctorate from Warwick
Prof. Adi Shamir (Weizmann Institute of Science), the world-renowned cryptographer and a recipient of the ACM Turing Award 2002 (the highest honour in computer science received jointly with Prof. Ronald Rivest and Prof. Leonard M. Adleman), visited our campus in January 2023 to collect an Honorary Doctorate from the University of Warwick. During his visit, Prof. Shamir gave also a research talk at the DIMAP seminar and CS Colloquium entitled "Efficient Detection of High Probability Cryptanalytic Properties of Boolean Functions."
Prof. Shamir has been known in Warwick since 1976, when he spent a year as a post-doc with our own Prof. Mike Paterson. Directly after Warwick Prof. Shamir went to MIT, where together with Adleman and Rivest he invented the famous RSA public-key cryptography algorithm for encoding and decoding messages, used nowadays by millions to securely transmit messages over the internet. The work on RSA has been immensely influential and led to the 2002 A.M. Turing Award for the three co-inventors, cited for the “ingenious contribution for making public-key cryptography useful in practice.” Other noticeable awards (for RSA and other numerous contributions to cryptography and computing) received by Prof. Shamir include the 2000 Institute of Electrical and Electronics Engineers Koji Kobayashi Computers and Communications Award, the Israel Mathematical Union Erdős Prize in Mathematics (1983), the Vatican Pontifical Academy PIUS XI Gold Medal (1992), the Association for Computing Machinery Paris Kannellakis Theory and Practice Award (1996), the Israel Prize in Computer Science (2008), and the Japan Prize in the field of electronics, information, and technology (2017), and the Foreign Member of the Royal Society (2018).